NDLI: Computing shortest paths among curved obstacles in the plane

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

A simple aggregative algorithm for counting triangulations of planar point sets and related problems

Efficiently hex-meshing things with topology

On a forgotten conjecture from a famous paper of Erdös

Graph induced complex on point data

Kinetic data structures for all nearest neighbors and closest pair in the plane

Recent progress on the combinatorial diameter of polyhedra and simplicial complexes

Complexity analysis of random geometric structures made simpler

On the 2-sum embedding conjecture

Range counting coresets for uncertain data

Counting and sampling minimum cuts in genus g graphs

Putting the turing into manufacturing: recent developments in algorithmic automation

A new approach to output-sensitive voronoi diagrams and delaunay triangulations

Ramsey-type results for semi-algebraic relations

Polyominoes on twisted cylinders

On soft predicates in subdivision motion planning

Zigzag zoology: rips zigzags for homology inference

A sub-quadratic algorithm for bipartite matching of planar points with bounded integer coordinates

Localized delaunay refinement for piecewise-smooth complexes

On planar point sets with the pentagon property

Homological reconstruction and simplification in $R^{3}$

Kinetic 2-centers in the black-box model

Union of random minkowski sums and network vulnerability analysis

Diverse near neighbor problem

Small-size relative (p,ε)-approximations for well-behaved range spaces

Topological graphs: empty triangles and disjoint matchings

A fast algorithm for well-spaced points and approximate delaunay graphs

Sharp bounds on Davenport-Schinzel sequences of every order

Interactive visualization of 3D configuration spaces

A near-optimal algorithm for shortest paths among curved obstacles in the plane

Geometry in the space of persistence modules

Lower bounds for k-distance approximation

A faster algorithm for computing motorcycle graphs

A parallel algorithm for computing the flow complex

Equal coefficients and tolerance in coloured tverberg partitions

Parameterized complexity of discrete morse theory

Competitive query strategies for minimising the ply of the potential locations of moving points

The maximum number of faces of the minkowski sum of three convex polytopes

Compressive sensing using locality-preserving matrices

A constant-factor approximation for multi-covering with disks

Bichromatic compatible matchings

Fast segment insertion and incremental construction of constrained delaunay triangulations

Capture bounds for visibility-based pursuit evasion

Parametric search visualization

Computing shortest paths among curved obstacles in the plane

Computing closed essential surfaces in knot complements

Systems of distant representatives in euclidean space

The graphs of planar soap bubbles

Hyperbolic delaunay complexes and voronoi diagrams made practical

Improved bounds for incidences between points and circles

Triangulating unknown environments using robot swarms

The complexity of separating points in the plane

A new approach to crushing 3-manifold triangulations

Robust geometric spanners

Point guards and point clouds: solving general art gallery problems

Computing shortest paths among curved obstacles in the plane

Content Provider	ACM Digital Library
Author	Wang, Haitao Chen, Danny Z.
Abstract	In this paper, we study the problem of finding Euclidean shortest paths among curved obstacles in the plane. We model curved obstacles as splinegons. A splinegon can be viewed as replacing each edge of a polygon by a convex curved edge, and each curved edge is assumed to be of O(1) complexity. Given in the plane two points s and t and a set of h pairwise disjoint splinegons with a total of n vertices, we present an algorithm that can compute a shortest path from s to t avoiding the splinegons in $O(n+hlog^{ε}h+k)$ time for any ε>0, where k is a parameter sensitive to the input splinegons and $k=O(h^{2}).$ If all splinegons are convex, a common tangent of two splinegons is "free" if it does not intersect the interior of any splingegon; our techniques yield an output sensitive algorithm for computing all free common tangents of the h splinegons in O(n+hlogh+k) time and O(n) working space, where k is the number of all free common tangents.
Starting Page	369
Ending Page	378
Page Count	10
File Format	PDF
ISBN	9781450320313
DOI	10.1145/2462356.2462377
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-06-17
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Relevant visibility graphs Curved obstacles Voronoi diagrams Splinegons Shortest paths Tangent graphs
Content Type	Text
Resource Type	Article

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

Computing Shortest Paths among Curved Obstacles in the Plane

Computing Shortest Paths among Curved Obstacles in the Plane∗

A near-optimal algorithm for shortest paths among curved obstacles in the plane

Two-site Voronoi diagrams in geographic networks

Computing L1 Shortest Paths among Polygonal Obstacles in the Plane (2012)

Shortest paths among obstacles in the plane

Shortest Paths in the Plane with Obstacle Violations

Computing Shortest Paths among Curved Obstacles in the Plane

On realistic terrains

Computing shortest paths among curved obstacles in the plane

Similar Documents

Computing Shortest Paths among Curved Obstacles in the Plane

Computing Shortest Paths among Curved Obstacles in the Plane∗

A near-optimal algorithm for shortest paths among curved obstacles in the plane

Two-site Voronoi diagrams in geographic networks

Computing L1 Shortest Paths among Polygonal Obstacles in the Plane (2012)

Shortest paths among obstacles in the plane

Shortest Paths in the Plane with Obstacle Violations

Computing Shortest Paths among Curved Obstacles in the Plane

On realistic terrains

Computing shortest paths among curved obstacles in the plane