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

Date

2013-01-01

Author

Hershberger, John
Suri, Subhash
Yıldız, Hakan

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

67
views

1
downloads

We propose an algorithm for the problem of computing shortest paths among curved obstacles in the plane. If the obstacles have O(n) description complexity, then the algorithm runs in O(nlogn) time plus a term dependent on the properties of the boundary arcs. Specifically, if the arcs allow a certain kind of bisector intersection to be computed in constant time, or even in O(logn) time, then the running time of the overall algorithm is O(n log n). If the arcs support only constant-time tangent, intersection, and length queries, as is customarily assumed, then the algorithm computes an approximate shortest path, with relative error ε, in time O(nlogn + nlog 1/ε). In fact, the algorithm computes an approximate shortest path map, a data structure with O(n logn) size, that allows it to report the (approximate) length of a shortest path from a fixed source point to any query point in the plane in O(logn) time. Copyright 2013 ACM.

URI

https://hdl.handle.net/11511/94000

DOI

https://doi.org/10.1145/2462356.2462374

Conference Name

29th Annual Symposium on Computational Geometry, SoCG 2013

Collections

Department of Computer Engineering, Conference / Seminar

Suggestions

OpenMETU
Core

A NEAR-OPTIMAL ALGORITHM FOR SHORTEST PATHS AMONG CURVED OBSTACLES IN THE PLANE Hershberger, John; Suri, Subhash; Yıldız, Hakan (2022-01-01) © 2022 Society for Industrial and Applied Mathematics.We propose an algorithm for the problem of computing shortest paths among curved obstacles in the plane. If the obstacles have O(n) description complexity, then the algorithm runs in O(n log n) time plus a term dependent on the properties of the boundary arcs. Specifically, if the arcs allow a certain kind of bisector intersection to be computed in constant time, or even in O(log n) time, then the running time of the overall algorithm is O(n log n). If t...
A 2-0 navier-stokes solution method with overset moving grids Tuncer, İsmail Hakkı (1996-01-01) A simple, robust numerical algorithm to localize moving boundary points and to interpolate uniteady solution variables across 2-D, arbitrarily overset computational grids is presented. Overset grids are allowed to move in time relative to each other. The intergrid boundary points are localized in terms of three grid points on the donor grid by a directional search algorithm. The parameters of the search algorithm give the interpolation weights at the localized boundary point. The method is independent of nu...
An algorithm for line matching in an image by mapping into an n-dimensional vector space Sultanov, Raiymbek; Atakan, Ahmet; Ismailova, Rita (2019-01-01) This paper proposes a minimal length difference algorithm for construction of a line in an image by solving the problem of optimal contour approximation. In this algorithm, a method for finding interest points is proposed, and the object matching (classification) is done by mapping interest points onto a vector space. In cases where the lines in the representation of the images are not smooth, the algorithm converges rapidly. The results of the experiments showed that for convergence of the contour simplifi...
A 2-D unsteady Navier-Stokes solution method with overlapping/overset moving grids Tuncer, İsmail Hakkı (1996-01-01) A simple, robust numerical algorithm to localize intergrid boundary points and to interpolate unsteady solution variables across 2-D, overset/overlapping, structured computational grids is presented. Overset/ overlapping grids are allowed to move in time relative to each other. The intergrid boundary points are localized in terms of three grid points on the donor grid by a directional search algorithm. The final parameters of the search algorithm give the interpolation weights at the interpolation point. Th...
A two-level iterative scheme for general sparse linear systems based on approximate skew-symmetrizers Mehrmann, Volker; Manguoğlu, Murat (2021-01-01) We propose a two-level iterative scheme for solving general sparse linear systems. The proposed scheme consists of a sparse preconditioner that increases the norm of the skew-symmetric part relative to the rest and makes the main diagonal of the coefficient matrix as close to the identity as possible so that the preconditioned system is as close to a shifted skew-symmetric matrix as possible. The preconditioned system is then solved via a particular Minimal Residual Method for Shifted Skew-Symmetric Systems...

Citation Formats

J. Hershberger, S. Suri, and H. Yıldız, “A near-optimal algorithm for shortest paths among curved obstacles in the plane,” presented at the 29th Annual Symposium on Computational Geometry, SoCG 2013, Rio de Janeiro, Brezilya, 2013, Accessed: 00, 2021. [Online]. Available: https://hdl.handle.net/11511/94000.