کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414718 | 681013 | 2012 | 10 صفحه PDF | دانلود رایگان |
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+ϵ)O(n3+ϵ) space. Our approach also extends to the case where query points should lie on a given set of line segments.
Journal: Computational Geometry - Volume 45, Issue 7, August 2012, Pages 284–293