Divide-and-Conquer Algorithm for Two-Point Shortest Path Queries in Polygonal Domains
In this research presented at SoCG 2019, a new divide-and-conquer algorithm is proposed for efficiently handling two-point shortest path queries in polygonal domains. The algorithm offers significant improvements in preprocessing space and query time compared to previous methods, making it a valuable contribution to computational geometry. The main idea involves finding gateways for query points to determine the shortest path by dividing the problem into smaller parts. Additionally, a path-preserving graph is utilized for finding a single shortest path in the domain. Overall, this work showcases advancements in solving geometric shortest path problems efficiently.
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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
A Divide-and-Conquer Algorithm for Two-Point ?1 Shortest Path Queries in Polygonal Domains Haitao Wang Utah State University SoCG 2019, Portland, Oregon
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
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 in the L1metric t s
Previous work and our results Previous work and our results Previous work (Chen, Klenk, Tu 2000): preprocessing: O(n2logn) space and O(n2log2n) time query: O(log2n) time Previous work (Chen, Inkulu, Wang 2014): preprocessing: O(n+ h2logh 4log ) space and O(n+ h2log2h 4log ) time query: O(log n) time Our new result: preprocessing: O(n+ h2log3h / loglog h) space and O(n+ h2log4h / loglog h) time query: O(log n) time A super-polylogarithmic but sublinear improvement
The main idea The main idea Given two query points s and t find m gateways for s, and m gateways for t A shortest s-t path is the concatenation of the following three parts: the segment from s to a gateway p* of s, a shortest path from p* to a gateway q* of t, the segment from q to t How to find p* and q*? Previous work: use a gateway graph of m2 edges a shortest path from p* to q* p* O(m2) time New result: a divide and conquer algorithm t s O(m log m) time q* gateways of s gateways of t
A A path path- -preserving preserving graph shortest path (Clarkson, Kapoor, Vaidya, 87 ) shortest path (Clarkson, Kapoor, Vaidya, 87 ) graph G G for finding a single for finding a single The node set of G: all obstacle vertices and some 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 projection of v on ? is a Steiner point do this recursively for the vertices to the left and right of ? ? cut-line Every two adjacent Steiner points on ? define an edge of G if they are mutually visible t s
The The cut cut- -line tree line tree: O(log n) height : O(log n) height G has O(nlogn) nodes and edges G contains a shortest path from s to t
Answering two Answering two- -point queries point queries Key idea: insert s and t to G (Chen et al. 00 ) insert Steiner points: connect to G via O(log n) ``gateways for each of s and t s
Finding a shortest s Finding a shortest s- -t path using gateways t path using gateways m gateways for s, and m gateways for t A straightforward solution (previous work): use a gateway graph of m2 edges O(m2) time Previous work (Chen, Klenk, Tu 2000): m = O(log n), query time: O(log2n) time Previous work (Chen, Inkulu, Wang 2014): use a larger graph m = O( log?), query time: O(log n) Our algorithm: O(m log m) time m = log n / loglog n, query time: O(log n) t s gateways of s gateways of t
Our divide Our divide- -and and- -conquer algorithm conquer algorithm a shortest path from p* to q* p* q* s t
Our divide Our divide- -and and- -conquer algorithm: conquer algorithm: an ideal scenario an ideal scenario Assume p* is in the first quadrant of s The algorithm will be applied to each quadrant of s Goal: For each gateway pi of s, find a shortest pi-t path using the gateways of t Find a shortest path from p1 to t: O(m) time Do the same for pk Pick the middle gateway pk/2 Find a shortest pk/2 t path q1 qi p1 t pi Pk/2 qk qk/2 pk s Work on the gateways of s on the two sides of pk/2 recursively
Ideal vs. non Ideal vs. non- -ideal ideal q1 q1 p1 p1 t gateway region pk pk s s non-ideal ideal
Ideal vs. non Ideal vs. non- -ideal ideal p1 p1 t t qk qk pk pk s s non-ideal ideal
Ideal vs. non Ideal vs. non- -ideal ideal q1 q1 qk/2 p1 p1 t t Pk/2 qk Pk/2 qk qk/2 pk s pk s non-ideal ideal
Dealing with the non Dealing with the non- -ideal cases ideal cases q1 p1 pi shortest path from pi to q1 t R(s) gateway region pk s For each pi, if d(p1, pi) + d(pi, q1) = d(p1, q1) then the blue path plus q1t is a shortest path from pi to t Find the largest index pi with the property
p pi i now playing the role of p now playing the role of p1 1 q1 p1 pi t R(s) pk s Non-ideal case: the orange path intersects the interior of R(s) The non-ideal case happens iff the first edge intersects the bottom side of R(s) which can be determined in constant time if yes, then all gateways after pi can be ignored: none of them can be p*, and we are done
Dealing with the non Dealing with the non- -ideal cases ideal cases run recursively q1 p1 pi q t pmiddle p* q* qk pj R(s) pk s run recursively
Remark Remark Similar divide-and-conquer has been used in planar graphs for two- vertex shortest path queries Gateways are vertices on separators, which are known already in the input Some work can be done on the gateways during the preprocessing Our problem Gateways are determined during query time
Thank you for your attention! Thank you for your attention!
