NDLI: Maximum thick paths in static and dynamic environments

Please wait, while we are loading the content...

Dynamic coresets

Tighter bounds for random projections of manifolds

The complexity of the outer face in arrangements of random segments

A (slightly) faster algorithm for klee's measure problem

I/o-efficient efficient algorithms for computing contours on a terrain

Exact geometric-topological analysis of algebraic surfaces

On the complexity of checking self-duality of polytopes and its relations to vertex enumeration and graph isomorphism

Arrangements of geodesic arcs on the sphere

Towards persistence-based reconstruction in euclidean spaces

Locally uniform anisotropic meshing

A simple and efficient kinetic spanner

Fast enumeration algorithms for non-crossing geometric graphs

Consistent digital rays

Delaunay triangulations of polyhedral surfaces, a discrete Laplace-Beltrami operator and applications

Optimizing active ranges for consistent dynamic map labeling

Markov convexity and local rigidity of distorted metrics

On s-intersecting curves and related problems

Walking your dog in the woods in polynomial time

External memory planar point location with logarithmic updates

Predicates for line transversals to lines and line segments in three-dimensional space

New existence proofs ε-nets

Delpsc: a delaunay mesher for piecewise smooth complexes

Reeb spaces of piecewise linear mappings

Discrete laplace operator on meshed surfaces

Schnyder woods for higher genus triangulated surfaces

Polychromatic colorings of plane graphs

Combinatorial genericity and minimal rigidity

Geometry is everywhere, part XLVII: metrics, nets, dimensions, and measures

Maximum thick paths in static and dynamic environments

Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs

On levels in arrangements of curves, iii: further improvements

Hinged dissections exist

Self-improving algorithms for delaunay triangulations

Robust construction of the three-dimensional flow complex

Extremal problems on triangle areas in two and three dimensions

On the computation of 3d periodic triangulations

Testing contractibility in planar rips complexes

Untangling triangulations through local explorations

Embedding and similarity search for point sets under translation

Coloring $k_{k}-free$ intersection graphs of geometric objects in the plane

Improved upper bounds on the crossing number

Circular partitions with applications to visualization and embeddings

Helly-type theorems for approximate covering

Markov incremental constructions

Visualizing and exploring planar algebraic arrangements: a web application

Approximating the pathway axis and the persistence diagram of a collection of balls in 3-space

Delaunay triangulations of imprecise pointsin linear time after preprocessing

Intersecting convex sets by rays

Analyzing rigidity with pebble games

Minkowski sums of rotating convex polyhedra

Routing a maximum number of disks through a scene of moving obstacles

Maximum thick paths in static and dynamic environments

Content Provider	ACM Digital Library
Author	Polishchuk, Valentin Arkin, Esther M. Mitchell, Joseph S.B.
Abstract	We consider the problem of finding a maximum number of disjoint paths for unit disks moving amidst static or dynamic obstacles. For the static case we give efficient exact algorithms, based on adapting the "continuous uppermost path" paradigm. As a by-product, we establish a continuous analogue of Menger's Theorem. (In this extended abstract we only state these results.) Next we study the dynamic problem in which the obstacles may move, appear and disappear, and otherwise change with time in a known manner; in addition, the disks are required to enter/exit the domain during prescribed time intervals. We observe that (unless P=NP), for any α,β > 0, one cannot decide in polynomial time whether there exist [αΚ] paths for disks of radius βR, where K is the maximum number of paths for radius-R disks. The problem is hard even if the obstacles are static, and only the entry/exit time intervals are specified for the disks. This motivates studying "dual" approximations, compromising on the radius of the disks and on the maximum speed of motion. Our main result is a pseudopolynomial-time dual-approximation algorithm: if K unit disks, each with unit bound on the speed, may be routed through an environment, our algorithm finds (at least) K paths for disks of radius Ω(1) moving with speed O(1). The algorithm computes a maxflow with "forbidden pairs" in an "adaptive" grid, laid out in space-time. Although (as we show) in general finding even an approximation to the maxflow with forbidden pairs is not possible (unless P=NP), a careful choice of time discetization and a non-uniform grid of "way-points" allows us to give provable approximation guarantees on the quality of the solution produced by the algorithm. Our algorithm extends to higher dimensions and to finding paths for translational motion of arbitrary-shape objects.
Starting Page	20
Ending Page	27
Page Count	8
File Format	PDF
ISBN	9781605580715
DOI	10.1145/1377676.1377682
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2008-06-09
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Motion planning Approximation algorithms
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in