Shortest Path Queries in Polygonal Domains and Free Space
Explore the challenges in designing data structures for efficient shortest path queries in polygonal domains with disjoint obstacles and free spaces. Discover the methodologies and results of previous works in this domain and examine related works impacting the query time complexity. Delve into the construction of a graph for finding single shortest paths in complex geometric spaces.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Two Two- -Point Point ??Shortest Path Queries in Shortest Path Queries in the Plane the Plane Danny Z. Chen1Rajasekhar Inkulu2Haitao Wang3 1University of Notre Dame 2Indian Institute of Technology 3Utah State University SoCG 2014
A polygonal domain A polygonal domain A set of h disjoint polygonal obstacles with a total of n vertices Free space: the space outside the obstacles h<<n is possible
Two Two- -point shortest path queries point shortest path queries Design a data structure to find a shortest path in the free space for any two query points s and t t s
Measuring the path length by the Measuring the path length by the ?? metric metric vertical length horizontal length the ?1length of the segment = the horizontal length + the vertical length
Previous work and our results Previous work and our results Previous work: preprocessing: O(n2logn) space and O(n2log2n) time query: O(log2n + k) time Chen, Klenk, Tu 2000 Our results: preprocessing: O(n+ h2logh 4log ) space and O(n+ h2log2h 4log ) time query: O(log n) time both bounded by O(n+h2+ )
Other related work Other related work The ?2case O(log n) time query with O(n11) preprocessing space O(log2n ) time query with O(n10logn) preprocessing space Chiang and Mitchell, 1999 if both s and t are on obstacle edges preprocessing: O(n5poly(log n)) space query: O(log n) time Bae and Okamato, 2012 For simple polygons (both ?1and ?2): preprocessing: O(n) time and space query: O(log n) time Guibas and Hershberger, 1989
A graph A graph G G for finding a single shortest for finding a single shortest path (Clarkson, Kapoor, Vaidya, 87 ) path (Clarkson, Kapoor, Vaidya, 87 ) The node set of G: all obstacle vertices and two types of Steiner points Type-1 Steiner points: project each vertex to the left, right, up, down t for each obstacle edge, every two adjacent Steiner points define an edge in G v s a type-1 Steiner point
Type Type- -2 Steiner points 2 Steiner points Draw a vertical line ? through the median x-coordinate of all vertices for each vertex v, if v is horizontally visible to ?, then the horizontal projection of v on ? is a type-2 Steiner point do this recursively on the left and right of ? ? cut-lines Every two adjacent Steiner points on ? define an edge of G if they are mutually visible
The The cut cut- -line tree line tree: O(log n) height : O(log n) height G contains a shortest path between s and t G has O(nlogn) nodes and edges
Answering two Answering two- -point queries point queries Key idea: insert s and t back to G (Chen et al. 00 ) insert type-1 Steiner points connect to G via eight ``gateways for each of s and t t s two gateways
Insert type Insert type- -2 Steiner points 2 Steiner points t connect t to G via O(log n) gateways
The gateway graph The gateway graph O(log n) nodes and O(log2n) edges finding a shortest path in O(log2 n) time In the preprocessing, shortest paths for all pairs of nodes are computed. The lengths of the orange edges are available during queries t s Remark: this approach can find (s,t) if (s,t) contains an obstacle vertex O(log n) gateways
Reducing the query time to O(log n) Reducing the query time to O(log n) Idea: using only O( log?) gateways How to do this? add more Steiner points on the cut-line tree make sure every log? levels have a new gateway v t obstacle vertex level numbers: 6 4 3 1
A new graph A new graph G G : Inserting points on the cut points on the cut- -line : Inserting more Steiner more Steiner line tree tree Partition the cut-line tree into O( log?) super- levels and each has log? levels log? levels O( log?) super levels log? levels log? levels
Insert more Steiner points Insert more Steiner points Consider a sub-tree in any super-level v
The new graph G The new graph G The size: O(? log?2log ?) Each vertex defines O(2log ?) Steiner points in each super-level Preprocessing: O(n2logn 4log ?) space Query: O(log n) time Next task: reduce the preprocessing to O(n+ h2logh 4log ) space even more challenging!!
The convex case: all obstacles are The convex case: all obstacles are convex convex Only consider the extreme vertices for building the graph O(h) such extreme vertices in total log ) size of the graph: O(h log 2
Non Non- -convex case convex case A special case: assume their convex hulls are pairwise disjoint The general case can be reduced to this special case using the extended corridor structure The ocean M: the free space outside the convex hulls Bays: free space not in M bays
Answering queries Answering queries Both s and t are in M M contains a shortest path Build a graph GMon all convex hulls size of GM: O(h log 2log ) t s
Query points are in bays Query points are in bays ?? Determine an intermediate point p on the gate, such that p is in (s,t) Find (s,p) in the bay Find (p,t) in the ocean M (s,t) = (s,p) U (p,t) easy: the bay is a simply polygon using the graph GM the bay gate p t s
Determine intermediate points on the Determine intermediate points on the bay gate bay gate v1: the first point vertically visible to ab if we go from s to a on (s,a) If (s,t) crosses az1, there exists a shortest path (s,t) containing z1 as an intermediate point If (s,t) crosses bz2, then z2 is an intermediate point b s z2 v2 v1 z1 a
The remaining case: All The remaining case: All ( (s,t z z1 1z z2 2 s,t) cross ) cross There exists (s,t) contains a particular point z z: the intersection of the line containing v1z1and the line containing v2z2 However, z is not on ab have to use other techniques b s z2 z v2 type-1 Steiner points v1 build a graph on these Steiner points merge the graph with GM z1 a
Our techniques extended to the Our techniques extended to the weighted rectilinear case weighted rectilinear case The obstacle edges are axis-parallel Each obstacle allows the path to travel through with a weight s t
Results for the weighted rectilinear Results for the weighted rectilinear case case Previous work: preprocessing: O(n2log2n) time and space query: O(log2n) time Chen, Klenk, Tu 2000 Our results: preprocessing: O(n2logn 4log ?) space and O(n2log2n 4log ?) time query: O(log n) time both bounded by O(n2+ )
Thank You Thank You
