Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
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
58
views
1
downloads
Cite This
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
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
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.