Quickest Visibility Queries in Polygonal Domains - Summary & Previous Work

Quickest Visibility Queries in Polygonal Domains Haitao Wang Utah State University SoCG 2017, Brisbane, Australia

Shortest paths Shortest paths queries in queries in a polygonal domain a polygonal domain A polygon P of h holes with a total of n vertices, a source point s Given a query point t, find a shortest path from s to reach t t s

Our problem: Our problem: Quickest Quickest visibility queries visibility queries Given a query point t, find a shortest path from s to see t a t s b

A A subproblem subproblem: shortest : shortest- -path path- -to to- -segment queries segment queries Given a query segment t, find a shortest path from s to any point of t q is a closest point of t to s q t s

Why a Why a subproblem subproblem? ? To answer a quickest visibility query for t Compute the visibility polygon Vis(t) of t Find a closest point q on the boundary of Vis(t) Observation: q must be on a window of t a window b Vis(t) a q The quickest visibility query can be solved by computing a closest point in each window of t, using the shortest path to segment queries t s

The simple polygon case is easier The simple polygon case is easier Observation: Only one window needs to be considered Difficulty for polygons with holes: have to consider many windows s t s q t

A polygonal domain A polygonal domain A polygon P of h holes with a total of n vertices h could be much smaller than n Complexities are better measured by h instead of n O(n2) vs. O(n + h2) h = 3 n = 32

Previous work: Simple polygons Previous work: Simple polygons Shortest-path-to-segment queries Arkin et al. 2015, Chiang and Tamassia 1997 Preprocessing time and space: O(n) Query time: O(log n) Quickest visibility queries Arkin et al. 2015 Preprocessing time and space: O(n) Query time: O(log n) Apply the shortest-path-to-segment query on the single window

Previous Previous work and our result: Polygonal domains work and our result: Polygonal domains Shortest-path-to-segment queries Preprocessing Space Query time O(n2 2 (n) log n) O(n2 2 (n) log n) O(log2 n) Arkin et al. 2015 O(n3log n) O(n3log n) O(log n) Arkin et al. 2015 O(n) O(n) O(h log n/h) This talk Assume SPM(s) has been computed in O(n log n) time Quickest visibility queries Preprocessing Space Query time O(n2 2 (n) log n) O(n2 2 (n) log n) O(K log2 n) Arkin et al. 2015 O(n8 log n) O(n7) O(log n) Arkin et al. 2015 O(n log h + h2 log h) O(n log h + h2) O(h log h log n) This talk K: the size of the visibility polygon Vis(t) of the query point t, and K = O(n)

The Quickest Visibility Queries The Quickest Visibility Queries - - O(h log h log n) O(h log h log n) time time A preliminary result: O((K+h) log h log n) query time First, compute Vis(t) and find all O(K) windows O(K h log n/h) time, if applied our shortest-path-to-segment queries on each window Reduce the time to O((K+h) log h log n) Goal: find a closest point q in all windows q t s

Extended Extended- -windows windows Extended-windows: Extend each window to t q is also the closest point on extended-windows Assumption: q is not an endpoint of these extended-windows Otherwise, find a shortest path from s to each endpoint Observation: if q is on an extended-window w, then (s,q) arrives at q from the left or the right side of w S1: The set of points on all extended-windows whose shortest paths are from the left side q1: a closest point in S1 q2: a closest point for the right side q is either q1 or q2 Assume q is q1 w q t s

Computing q (= q Computing q (= q1 1) ) Prune some (parts of) extended-windows For an extended-window w, if we know that a sub-segment w of w does not contain a closest point, then w can be pruned Observation: For any point p on an extended-window, if (s,p) intersects another extended-window, then p cannot be a closest point and can be pruned p a t s

The pruning principle The pruning principle Consider two extended-windows ta and tb, and three shortest paths from: (s,a), (s,b), (s,t) Case 1: no pruning can be done Case 2: the entire tb can be pruned Case 3: the sub-segment tc can be pruned b a b a a b c p p s s s t t t Case 1 Case 3 Case 2

An example and the algorithm An example and the algorithm Step 1: Pruning Step 2: Compute a closest point from s to each remaining sub-segment O((K+h) log h log n) time in total 6 5 4 2 8 7 3 1 9 s t 10

Reducing the query time: Reducing the query time: O(( O( O(h h log h log n) log h log n) O((K+h K+h) log h log n) ) log h log n) Main Idea: Instead of Vis(t), only compute a special subset S(t) of O(h) windows Lemma: a closest point q must be on a window of S(t) Apply the preliminary algorithm on all windows of S(t) How to find S(t)? Extended corridor structure

Defining the window set S(t) Defining the window set S(t) q s a t

Defining the window set S(t) Defining the window set S(t) q b s a t t

Thank you for your attention! Thank you for your attention! 6 5 4 2 8 7 3 1 9 s t 10

Shortest Shortest- -path path- -to to- -segment queries segment queries Our approach: Using a decomposition D of P Bisectors of the shortest path map SPM(s) of s V: the set of all intersections between bisectors and obstacles, and triple points (intersections of bisectors) All shortest paths from s to all points of V Remove all bisectors The resulting decomposition is D b a s

Important properties of the decomposition D Important properties of the decomposition D D can be computed in O(n) time from SPM(s) Each cell is simply connected After O(n) time preprocessing, given any segment t in a cell C, a shortest path from s to t can be computed in O(log |C|) time For any segment t, t can intersect O(h) cells For any segment t in P, the shortest path from s to t can be computed in O(h log n/h) time by a pedestrian algorithm t b a t s

Important properties of the decomposition D Important properties of the decomposition D D can be computed in O(n) time from SPM(s) Each cell is simply connected Each cell C has two super-roots r1 and r2, such that for any point t in C, the shortest s-t path is the concatenation of a shortest s-r path and a shortest r-t path in C, for some super-root r After O(n) time preprocessing, given any segment t in a cell C, a shortest path from s to t can be computed in O(log |C|) time For any segment t, t can intersect O(h) cells For any segment t in P, the shortest path from s to t can be computed in O(h log n/h) time by a pedestrian algorithm t r2 t b a t r1 s

The pruning principle The pruning principle Consider two extended-windows ta and tb, and three shortest paths from: (s,a), (s,b), (s,t) Case 1: no pruning can be done Case 2: the entire tb can be pruned Case 3: the sub-segment tc can be pruned b a b a a b c p p s s s t t t Case 1 Case 3 Case 2

An example and the algorithm An example and the algorithm Step 1: Pruning Step 2: Compute a closest point from s to each remaining sub-segment O((K+h) log h log n) time using the decomposition D only need to consider O(h) cells of D 6 5 4 2 8 7 3 1 9 s t 10

A summary on the preliminary result A summary on the preliminary result O(n log h) If the windows are given Preprocessing time: O(n log h + h2 log h) Space: O(n log h + h2) Query time: O((K+h) log h log n) The quadratic preprocessing is only for computing the windows of t O(n log h) A new problem: Given a query set of k=O(n) segments in P intersecting at a point t, find the closest point on these segments Preprocessing time and space: O(n log h) Query time: O((k+h) log h log n) q s t