Ch.15: Visibility Graphs

From "Computational Geometry: Algorithms and Applications", 3rd edition (Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars) 15.1. Shortest Paths for a Point Robot 15.2. Computing the Visibility Graph 15.3. Shortest Paths for a Translating Polygonal Robot 15.4. Notes and Comments

41 flashcards · Mathematics · by lakesare

Part of Textbooks › Computational Geometry: Algorithms and Applications (de Berg et al.) · 16 courses

[Visibility Graphs] What does the chapter on visibility graphs compute, and why is the path-planning method based on trapezoidal maps (motion planning chapter) not enough?
A Euclidean shortest collision-free path for a translating planar robot. The trapezoidal-map method always finds a path if one exists, but the path may make a large detour or many unnecessary turns; a robot on a factory floor transports less per time unit on a long path. A shortest path for a translating robot.
[Visibility Graphs] For a robot that can only move in straight lines (it must stop and rotate to change direction), what besides path length matters, and does the visibility-graph chapter take it into account?
The number of turns on the path. No: the chapter minimizes only the Euclidean length.
[Shortest Paths for a Point Robot] SSS is a set of disjoint simple polygons (obstacles, open sets) in the plane with nnn edges in total; a point robot moves from pstartp_{\text{start}}pstart to pgoalp_{\text{goal}}pgoal in the free space.Why must the obstacles be open sets for a shortest path to exist?
With closed obstacles, every path could be shortened by moving closer to an obstacle. So no shortest path would exist, unless the robot can go to the goal in a straight line.Open obstacles let the robot touch them. A shortest path need not be unique, so the book says a shortest path.
[Shortest Paths for a Point Robot] The trapezoidal map of the free space gives a road map Groad\mathcal{G}_{\text{road}}Groad (nodes at trapezoid centers and on the vertical extensions). Why does it not give a shortest path, even with Euclidean arc weights and Dijkstra's algorithm?
The path is forced through the road map's nodes, so a shortest path in the road map can differ from the real shortest path. Breadth-first search (as used for plain path planning) even minimizes only the number of arcs, which can be far apart or close together. The road-map path passes below the triangle; the real shortest path passes above it.
[Shortest Paths for a Point Robot] A vertex of a polygonal path that is not its begin- or endpoint is an inner vertex.
[Shortest Paths for a Point Robot] Lemma 15.1 Let SSS be a set of disjoint polygonal obstacles. Any shortest path between pstartp_{\text{start}}pstart and pgoalp_{\text{goal}}pgoal among SSS is … ?
A polygonal path whose inner vertices are vertices of SSS . Intuition: a rubber band released along any path contracts until the obstacles stop it; it then consists of straight segments through open space and pieces of obstacle boundaries.
[Shortest Paths for a Point Robot] When is a path locally shortest?
Every subpath between two of its points qqq and rrr is a shortest path from qqq to rrr . Every shortest path is locally shortest, otherwise replacing the subpath would shorten it.
[Shortest Paths for a Point Robot] SSS is a set of disjoint simple polygons (obstacles, open sets) in the plane with nnn edges in total; a point robot moves from pstartp_{\text{start}}pstart to pgoalp_{\text{goal}}pgoal in the free space.Why is a shortest path τ\tauτ from pstartp_{\text{start}}pstart to pgoalp_{\text{goal}}pgoal polygonal?
A curved piece at a point ppp in the open free space could be replaced by a straight chord inside a small free disc around ppp , which is shorter. The obstacles are polygonal, so a non-polygonal τ\tauτ has a point ppp in the interior of the free space that lies on no straight piece of τ\tauτ . The chord joins where τ\tauτ enters and leaves the disc; this contradicts τ\tauτ being locally shortest. The short cut inside the disc around ppp .
[Shortest Paths for a Point Robot] SSS is a set of disjoint simple polygons (obstacles, open sets) in the plane with nnn edges in total; a point robot moves from pstartp_{\text{start}}pstart to pgoalp_{\text{goal}}pgoal in the free space.Why must every inner vertex vvv of a shortest polygonal path be an obstacle vertex?
At any other point, a free (half-)disc around vvv allows a straight short cut of the turn. If vvv is in the interior of the free space, a whole disc around vvv is free; if vvv is in the relative interior of an obstacle edge, half a disc around vvv is free. Either way the subpath inside it can be replaced by a shorter segment. So only an obstacle vertex remains.
[Shortest Paths for a Point Robot] What is the visibility graph Gvis(S)\mathcal{G}_{\text{vis}}(S)Gvis(S) of a set SSS of disjoint polygonal obstacles?
Nodes: the vertices of SSS . Arcs: between every two vertices v,wv, wv,w that see each other, i.e. the segment vw‾\overline{vw}vw does not intersect the interior of any obstacle. A visibility graph (with pstartp_{\text{start}}pstart and pgoalp_{\text{goal}}pgoal added) and a shortest path along its arcs.
[Shortest Paths for a Point Robot] Two vertices that can see each other are called (mutually) visible, and the segment connecting them is a visibility edge.
[Shortest Paths for a Point Robot] The visibility graph Gvis(S)\mathcal{G}_{\text{vis}}(S)Gvis(S) of a set SSS of polygonal obstacles has the vertices of SSS as nodes, and an arc between vvv and www whenever the segment vw‾\overline{vw}vw does not intersect the interior of any obstacle.Are the obstacle edges arcs of Gvis(S)\mathcal{G}_{\text{vis}}(S)Gvis(S) ?
Yes: the two endpoints of an obstacle edge always see each other. The edge lies on the boundary, and the obstacles are open, so it misses their interiors.
[Shortest Paths for a Point Robot] Corollary 15.2 Let SSS be a set of disjoint polygonal obstacles. A shortest path between pstartp_{\text{start}}pstart and pgoalp_{\text{goal}}pgoal among SSS consists of arcs of which graph?
Arcs of the visibility graph Gvis(S∗)\mathcal{G}_{\text{vis}}(S^*)Gvis(S∗) , where S∗:=S∪{pstart,pgoal}S^* := S \cup \{p_{\text{start}}, p_{\text{goal}}\}S∗:=S∪{pstart,pgoal} . The inner vertices are obstacle vertices, so the inner segments are visibility edges; adding pstartp_{\text{start}}pstart and pgoalp_{\text{goal}}pgoal as vertices makes the first and last segment visibility edges too.
[Shortest Paths for a Point Robot] SSS is a set of disjoint simple polygons (obstacles, open sets) in the plane with nnn edges in total; a point robot moves from pstartp_{\text{start}}pstart to pgoalp_{\text{goal}}pgoal in the free space.What are the three steps of algorithm ShortestPath (S,pstart,pgoal)(S, p_{\text{start}}, p_{\text{goal}})(S,pstart,pgoal) ?
1. Compute the visibility graph Gvis\mathcal{G}_{\text{vis}}Gvis of S∪{pstart,pgoal}S \cup \{p_{\text{start}}, p_{\text{goal}}\}S∪{pstart,pgoal} . 2. Weight each arc (v,w)(v, w)(v,w) with the Euclidean length of vw‾\overline{vw}vw . 3. Run Dijkstra's algorithm from pstartp_{\text{start}}pstart to pgoalp_{\text{goal}}pgoal in Gvis\mathcal{G}_{\text{vis}}Gvis .
[Shortest Paths for a Point Robot] Obstacles with nnn edges in total, plus pstartp_{\text{start}}pstart and pgoalp_{\text{goal}}pgoal : what bounds the number kkk of arcs of the visibility graph?
k≤(n+22)=O(n2)\boldsymbol{k \le \binom{n+2}{2} = O(n^2)}k≤(2n+2)=O(n2) The graph has n+2n + 2n+2 nodes (a polygon has as many vertices as edges), and there is at most one arc per pair of nodes.
[Shortest Paths for a Point Robot] How fast does Dijkstra's algorithm find a shortest path between two nodes of a graph with nnn nodes and kkk arcs of non-negative weight?
O(nlog⁡n+k)\boldsymbol{O(n \log n + k)}O(nlogn+k) time This bound needs Fibonacci heaps. For shortest paths among obstacles an O((n+k)log⁡n)O((n + k) \log n)O((n+k)logn) implementation is fast enough too, since computing the visibility graph takes that long anyway.
[Shortest Paths for a Point Robot] Theorem 15.3. How fast can a shortest path between two points among polygonal obstacles with nnn edges in total be computed?
O(n2log⁡n)\boldsymbol{O(n^2 \log n)}O(n2logn) time Visibility graph: O(n2log⁡n)O(n^2 \log n)O(n2logn) . Arc weights: O(n2)O(n^2)O(n2) , since there are k=O(n2)k = O(n^2)k=O(n2) arcs. Dijkstra: O(nlog⁡n+k)=O(n2)O(n \log n + k) = O(n^2)O(nlogn+k)=O(n2) .
[Computing the Visibility Graph] SSS : disjoint polygonal obstacles with nnn edges in total. What is the naive way to compute the visibility graph, and how long does it take?
Test every pair of vertices against all obstacle edges: O(n2)O(n^2)O(n2) pairs times O(n)O(n)O(n) per test, so O(n3)O(n^3)O(n3) time. Testing one specific pair can't be done faster; the speed-up comes from treating all vertices seen from one vertex together.
[Computing the Visibility Graph] How does algorithm VisibilityGraph (S)(S)(S) build the visibility graph of a set SSS of disjoint polygonal obstacles?
For every vertex vvv of SSS , call VisibleVertices (v,S)(v, S)(v,S) and add an arc (v,w)(v, w)(v,w) for every returned vertex www . VisibleVertices (p,S)(p, S)(p,S) returns all obstacle vertices visible from a point ppp not in the interior of any obstacle ( ppp need not be a vertex).
[Computing the Visibility Graph] To find all obstacle vertices visible from a point ppp , in which order does VisibleVertices treat the vertices, and why?
In cyclic order around ppp , so that information from one vertex helps to decide the visibility of the next. The vertices visible from ppp .
[Computing the Visibility Graph] ρ\rhoρ is the half-line from a point ppp through an obstacle vertex www . In which two ways can www be invisible from ppp ?
1. ρ\rhoρ hits an obstacle edge before reaching www . 2. ppp and www are vertices of the same obstacle and pw‾\overline{pw}pw runs through its interior. Case 1: binary search with www among the edges intersected by ρ\rhoρ . Case 2: look at the two edges incident to www , to see whether ρ\rhoρ is inside the obstacle just before www . www is invisible: ρ\rhoρ crosses an edge of the left obstacle first.
[Computing the Visibility Graph] In VisibleVertices (sweep around a point ppp ), what does the balanced search tree T\mathcal{T}T store, at the leaves and at the interior nodes?
Leaves: the obstacle edges intersected by the half-line ρ\rhoρ from ppp , in the order along ρ\rhoρ (leftmost leaf = first edge hit). An interior node ν\nuν stores the rightmost edge eνe_\nueν of its left subtree: edges in the left subtree are ≤eν\le e_\nu≤eν along ρ\rhoρ , edges in the right subtree are greater. Edges e1,…,e6e_1, \dots, e_6e1,…,e6 intersected by ρ\rhoρ , and the tree on them.
[Computing the Visibility Graph] Treating the vertices in cyclic order around a point ppp while a half-line from ppp rotates is called a rotational plane sweep.
Like a plane sweep, but with a rotating half-line instead of a horizontal line moving downward.
[Computing the Visibility Graph] In the rotational plane sweep of VisibleVertices around a point ppp , what are the status and the events?
Status: the ordered sequence of obstacle edges intersected by the half-line ρ\rhoρ (kept in T\mathcal{T}T ). Events: the vertices of SSS . At an event www : decide whether www is visible by searching in T\mathcal{T}T , then insert and/or delete the obstacle edges incident to www .
[Computing the Visibility Graph] Where does the half-line ρ\rhoρ of VisibleVertices start, in which direction does it rotate around ppp , and how are vertices at the same angle ordered?
Starts pointing in the positive xxx -direction, rotates clockwise; equal angles: closer to ppp first. Vertices that may lie in the interior of pw‾\overline{pw}pw must be treated before www , since they decide whether pw‾\overline{pw}pw is blocked.
[Computing the Visibility Graph] How does VisibleVertices initialize the search tree T\mathcal{T}T before the sweep around ppp ?
Insert the obstacle edges properly intersected by the horizontal half-line ρ\rhoρ from ppp in the positive xxx -direction, in the order along ρ\rhoρ . Edges contained in ρ\rhoρ need not be stored.
[Computing the Visibility Graph] Rotational sweep around a point ppp to find the obstacle vertices visible from ppp : vertices w1,…,wnw_1, \dots, w_nw1,…,wn in clockwise order around ppp (ties: closer to ppp first); T\mathcal{T}T is a balanced search tree on the obstacle edges intersected by the half-line ρ\rhoρ from ppp , in the order along ρ\rhoρ .After deciding whether wiw_iwi is visible, how is T\mathcal{T}T updated?
Insert the edges incident to wiw_iwi on the clockwise side of the half-line from ppp to wiw_iwi ; delete those on the counterclockwise side. Clockwise-side edges start being crossed by ρ\rhoρ at wiw_iwi ; counterclockwise-side edges stop being crossed.
[Computing the Visibility Graph] Rotational sweep around a point ppp to find the obstacle vertices visible from ppp : vertices w1,…,wnw_1, \dots, w_nw1,…,wn in clockwise order around ppp (ties: closer to ppp first); T\mathcal{T}T is a balanced search tree on the obstacle edges intersected by the half-line ρ\rhoρ from ppp , in the order along ρ\rhoρ .Visible (wi)(w_i)(wi) : in the normal case (no earlier vertex on pwi‾\overline{pw_i}pwi ), which single check decides whether wiw_iwi is visi…
Whether the edge in the leftmost leaf of T\mathcal{T}T (the edge closest to ppp along ρ\rhoρ ) intersects pwi‾\overline{pw_i}pwi . If no such edge exists or it does not intersect pwi‾\overline{pw_i}pwi , wiw_iwi is visible. (This is after first checking that pwi‾\overline{pw_i}pwi does not enter wiw_iwi 's own obstacle.)
[Computing the Visibility Graph] Rotational sweep around a point ppp to find the obstacle vertices visible from ppp : vertices w1,…,wnw_1, \dots, w_nw1,…,wn in clockwise order around ppp (ties: closer to ppp first); T\mathcal{T}T is a balanced search tree on the obstacle edges intersected by the half-line ρ\rhoρ from ppp , in the order along ρ\rhoρ .What does Visible (wi)(w_i)(wi) check first, before looking at T\mathcal{T}T ?
Whether pwi‾\overline{pw_i}pwi intersects the interior of the obstacle of which wiw_iwi is a vertex, locally at wiw_iwi . If so, wiw_iwi is invisible. Decided from the two edges incident to wiw_iwi .
[Computing the Visibility Graph] Rotational sweep around a point ppp to find the obstacle vertices visible from ppp : vertices w1,…,wnw_1, \dots, w_nw1,…,wn in clockwise order around ppp (ties: closer to ppp first); T\mathcal{T}T is a balanced search tree on the obstacle edges intersected by the half-line ρ\rhoρ from ppp , in the order along ρ\rhoρ .The vertex wi−1w_{i-1}wi−1 lies on pwi‾\overline{pw_i}pwi . How does Visible (wi)(w_i)(wi) decide, and why is this correct?
If wi−1w_{i-1}wi−1 is invisible, so is wiw_iwi . Otherwise wiw_iwi is invisible iff wi−1wi‾\overline{w_{i-1}w_i}wi−1wi lies inside an obstacle having both as vertices, or an edge in T\mathcal{T}T intersects wi−1wi‾\overline{w_{i-1}w_i}wi−1wi . Correct because pwi‾=pwi−1‾∪wi−1wi‾\overline{pw_i} = \overline{pw_{i-1}} \cup \overline{w_{i-1}w_i}pwi=pwi−1∪wi−1wi ; the edges at vertices on pwi−1‾\overline{pw_{i-1}}pwi−1 were already inspected when those vertices were treated.
[Computing the Visibility Graph] Rotational sweep around a point ppp to find the obstacle vertices visible from ppp : vertices w1,…,wnw_1, \dots, w_nw1,…,wn in clockwise order around ppp (ties: closer to ppp first); T\mathcal{T}T is a balanced search tree on the obstacle edges intersected by the half-line ρ\rhoρ from ppp , in the order along ρ\rhoρ . wi−1w_{i-1}wi−1 is visible from ppp . Is wiw_iwi ?
No: an obstacle edge in T\mathcal{T}T crosses wi−1wi‾\overline{w_{i-1}w_i}wi−1wi .
[Computing the Visibility Graph] Rotational sweep around a point ppp to find the obstacle vertices visible from ppp : vertices w1,…,wnw_1, \dots, w_nw1,…,wn in clockwise order around ppp (ties: closer to ppp first); T\mathcal{T}T is a balanced search tree on the obstacle edges intersected by the half-line ρ\rhoρ from ppp , in the order along ρ\rhoρ . wi−1w_{i-1}wi−1 is visible from ppp . Is wiw_iwi ?
No: wi−1wi‾\overline{w_{i-1}w_i}wi−1wi lies inside the obstacle of which both are vertices.
[Computing the Visibility Graph] Rotational sweep around a point ppp to find the obstacle vertices visible from ppp : vertices w1,…,wnw_1, \dots, w_nw1,…,wn in clockwise order around ppp (ties: closer to ppp first); T\mathcal{T}T is a balanced search tree on the obstacle edges intersected by the half-line ρ\rhoρ from ppp , in the order along ρ\rhoρ . wi−1w_{i-1}wi−1 is visible from ppp . Is wiw_iwi ?
Yes: wi−1wi‾\overline{w_{i-1}w_i}wi−1wi is crossed by no edge in T\mathcal{T}T and lies in no obstacle, and pwi‾\overline{pw_i}pwi does not enter wiw_iwi 's obstacle at wiw_iwi .
[Computing the Visibility Graph] SSS : polygonal obstacles with nnn edges in total. What is the running time of VisibleVertices (p,S)(p, S)(p,S) , and where does it come from?
O(nlog⁡n)\boldsymbol{O(n \log n)}O(nlogn) Sorting the vertices around ppp : O(nlog⁡n)O(n \log n)O(nlogn) . Each of the nnn events: a constant number of O(log⁡n)O(\log n)O(logn) operations on T\mathcal{T}T plus constant-time geometric tests.
[Computing the Visibility Graph] Theorem 15.4. How fast can the visibility graph of a set of disjoint polygonal obstacles with nnn edges in total be computed?
O(n2log⁡n)\boldsymbol{O(n^2 \log n)}O(n2logn) time One O(nlog⁡n)O(n \log n)O(nlogn) rotational sweep (VisibleVertices) around each of the nnn vertices.
[Shortest Paths for a Translating Polygonal Robot] How is a shortest path computed for a convex polygonal robot R\mathcal{R}R that translates among polygonal obstacles?
Run the point-robot method on the configuration-space obstacles: the Minkowski sums of −R-\mathcal{R}−R with the obstacles. Their union, the forbidden configuration space, is a set of disjoint polygons. Add the start and goal placements as points, compute the visibility graph, weight arcs by Euclidean length, run Dijkstra. Work space, configuration space, visibility graph.
[Shortest Paths for a Translating Polygonal Robot] Theorem 15.5. R\mathcal{R}R is a convex, constant-complexity robot translating among polygonal obstacles with nnn edges in total. How fast can a shortest collision-free path from a start to a goal placement be computed?
O(n2log⁡n)\boldsymbol{O(n^2 \log n)}O(n2logn) time The forbidden space has complexity O(n)O(n)O(n) and is computed in O(nlog⁡2n)O(n \log^2 n)O(nlog2n) time; its visibility graph then takes O(n2log⁡n)O(n^2 \log n)O(n2logn) .
[Notes and Comments] Why does every shortest-path algorithm that first builds the whole visibility graph take at least quadratic time in the worst case, and what is the optimal bound for a point robot among polygonal obstacles with nnn edges?
The visibility graph can have Θ(n2)\Theta(n^2)Θ(n2) edges. Optimal: O(nlog⁡n)O(n \log n)O(nlogn) (Hershberger and Suri). Mitchell first broke the quadratic barrier with O(n5/3+ε)O(n^{5/3+\varepsilon})O(n5/3+ε) , later O(n3/2+ε)O(n^{3/2+\varepsilon})O(n3/2+ε) .
[Notes and Comments] What is the optimal running time for computing the visibility graph of polygonal obstacles with nnn edges, where kkk is its number of arcs?
O(nlog⁡n+k)\boldsymbol{O(n \log n + k)}O(nlogn+k) (Ghosh and Mount) The rotational-sweep algorithm with O(n2log⁡n)O(n^2 \log n)O(n2logn) time is due to Lee.
[Notes and Comments] How fast can a shortest path be computed when the free space is a simple polygon without holes?
In linear time: Chazelle's linear-time triangulation combined with the shortest-path method of Guibas et al.
[Notes and Comments] Why is the Euclidean shortest path problem among polyhedral obstacles in 3-dimensional space much harder, and how hard is it?
The bends of a shortest path can lie anywhere on obstacle edges, not in a finite set of points; the problem is NP-hard (Canny). So there is no easy discretization like the visibility graph.