2009/11/26 by Sang Won Bae, Yoshio Okamoto, Bae, Sang Won +1
Computer Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #F.2.2 #FOS: Computer and information sciences #Robotic Path Planning Algorithms #cs.CG
paper · pdf · doi:10.48550/arxiv.0911.5017
12 pages, 3 figures, an extended abstract presented at ISAAC 2009
arxiv created 2009/11/26 · openalex publication_date 2009/11/26 · arxiv updated 2009/12/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider a variant of two-point Euclidean shortest path query problem: given a polygonal domain, build a data structure for two-point shortest path query, provided that query points always lie on the boundary of the domain. As a main result, we show that a logarithmic-time query for shortest paths between boundary points can be performed using O~ (n5) preprocessing time and O(n5) space where n is the number of corners of the polygonal domain and the O~ notation suppresses the polylogarithmic factor. This is realized by observing a connection between Davenport-Schinzel sequences and our problem in the parameterized space. We also provide a tradeoff between space and query time; a sublinear time query is possible using O(n3+epsilon) space. Our approach also extends to the case where query points should lie on a given set of line segments.