A NEAR-OPTIMAL ALGORITHM FOR SHORTEST PATHS AMONG CURVED OBSTACLES IN THE PLANE

Date

2022-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

59
views

0
downloads

© 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 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(n log n + n log 1\e ). In fact, the algorithm computes an approximate shortest path map, a data structure with O(n log n) 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(log n) time. By applying an idea due to Wang [Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, 2021, pp. 810-821], the algorithm's working storage and the size of the approximate shortest path map can be reduced to O(n).

Subject Keywords

geometric obstacles, obstacle avoidance, planar subdivision, shortest path map, shortest paths

URI

https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85137634523&origin=inward
https://hdl.handle.net/11511/100846

Journal

SIAM Journal on Computing

DOI

https://doi.org/10.1137/21m1428248

Collections

Department of Computer Engineering, Article

Suggestions

OpenMETU
Core

A near-optimal algorithm for shortest paths among curved obstacles in the plane Hershberger, John; Suri, Subhash; Yıldız, Hakan (2013-01-01) 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,...
A Methodology for Resolution Mapping for Cross-Resolution Simulation using Event-B Kara, Ahmet; Oğuztüzün, Mehmet Halit S.; Alpdemir, M. Nedim (2015-11-01) This paper proposes a software engineering solution for implementing simulations via the composition of models at different resolution levels with the help of formal methods. Our solution provides a systematic methodology that offers a well-defined sequence of stages to obtain executable converters for entity resolution mapping, given the types of entity attributes that are exchanged at model interfaces and the mapping specifications. Our methodology uses Event-B as the formal specification language and Dis...
A Methodology for cross-resolution modeling in DEVS using event-B refinement Kara, Ahmet; Oğuztüzün, Mehmet Halit S.; Alpdemir, Mahmut Nedim; Department of Computer Engineering (2014) This thesis proposes a software engineering solution for implementing simulations via composition of models at different resolution levels with the help of formal methods. Our solution provides a systematic methodology that offers a well-defined sequence of stages to obtain executable converters for entity resolution mapping, given the types of entity attributes that are exchanged at model interfaces and the mapping specifications. Our methodology relies on Event-B as the formal specification language and D...
An algorithm to resolve the optimal locomotion problem of modular robots Mencek, Hakan; Soylu, Reşit; Department of Mechanical Engineering (2007) In this study, a novel optimal motion planning algorithm is developed for the locomotion of modular robots. The total energy consumption of the robot is considered to be the optimization criteria. In order to determine the energy consumption of the system, the kinematic and dynamic analyses of the system are performed. Due to the variable number of modules in the system, a recursive formulation is developed for both kinematic and dynamic analyses. Coulomb's static and dynamic friction models are used to mod...
An automatic geo-spatial object recognition algorithm for high resolution satellite images Ergul, Mustafa; Alatan, Abdullah Aydın (2013-09-26) This paper proposes a novel automatic geo-spatial object recognition algorithm for high resolution satellite imaging. The proposed algorithm consists of two main steps; a hypothesis generation step with a local feature-based algorithm and a verification step with a shape-based approach. In the hypothesis generation step, a set of hypothesis for possible object locations is generated, aiming lower missed detections and higher false-positives by using a Bag of Visual Words type approach. In the verification s...

Citation Formats

J. Hershberger, S. Suri, and H. Yıldız, “A NEAR-OPTIMAL ALGORITHM FOR SHORTEST PATHS AMONG CURVED OBSTACLES IN THE PLANE,” SIAM Journal on Computing, vol. 51, no. 4, pp. 1296–1340, 2022, Accessed: 00, 2022. [Online]. Available: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85137634523&origin=inward.