« nazaj
Computational geometry - Tutorial 24.3.2021
Sweeping algorithms
Exercise 1
Let $S$ be a set of $n$ circles in a plane. (A circle is a curve, i.e., the edge of a disk.) Describe an output-sensitive sweeping algorithm which reports all intersections between the circles in $S$ in $O((n+k) \log n)$ time, where $k$ is the number of reported intersections.
- input: sequence of circles given by $(p, r)$, where $p$ is a point in the plane and $r > 0$
- output: sequence of points with pointers to intersecting circles
- event queue: binary search tree (or a modified heap)
- leftmost points of circles
- rightmost points of circles
- intersections between circles
- state: binary search tree
- upper half-circles
- lower half-circles
- initialization:
- event queue: add leftmost and rightmost point of each circle ($O(n \log n)$)
- state: empty BST
- events ($O(n+k)$ steps, each taking $O(\log n)$):
- leftmost point:
- add upper and lower half-circles of the corresponding circle
- check for intersections with the neighboring half-circles and add them to the queue
- rightmost point:
- remove upper and lower half-circles of the corresponding circle
- check for intersections between the newly neighboring half-circles and add them to the queue
- intersection:
- report the intersection
- swap the intersecting half-circles
- check for intersections with the newly neighboring half-circles and add them to the queue
Exercise 2
Let $P$ and $Q$ be $x$-monotonous paths with $n$ and $m$ vertices, respectively. Assume that no $3$ vertices are collinear.
- Prove that $P \cap Q$ has cardinality at most $O(n+m)$.
- Describe an algorithm which computes $P \cap Q$ in linear time.
-
- For each pair of consecutive segments $s, s’ \in P$, there exists at most one segment from $Q$ intersecting both $s, s’$.
- The maximal number of intersections is $n+m-3 = O(n+m)$.
- Example list of intersections:
- $({p_1}, {q_1})$
- $({p_1}, {q_2})$ last
- $({p_2}, {q_2})$ last
- $({p_3}, {q_2})$
- $({p_3}, {q_3})$
- $({p_3}, {q_4})$ last
- $({p_4}, {q_4})$
-
- intialization: merge the two paths into a $x$-sorted list of points ($O(n+m)$)
- state: segments from $P$ and $Q$ the sweep line currently intersects
- events ($O(n+m)$):
- vertices of $P$
- vertices of $Q$
- action at vertex from $R \in \lbrace P, Q \rbrace$ ($O(1)$):
- replace the segment from $R$ in the state with the next segment
- check for the intersection with the other segment in the state
Exercise 3
Let $S$ be a set of $n$ pairwise disjoint segments in a plane, and let $p$ be a point not lying on any segment from $S$. Let $S(p)$ be the subset of the segments in $S$ which are partially visible from $p$ - i.e., a segment $s \in S$ is in $S(p)$ if and only if there is a point $q \in s$ such that $\overline{pq} \cap s’ = \emptyset$ for each $s’ \in S \setminus \lbrace s \rbrace$. Describe an algorithm which computes $S(p)$.
Hint: a sweeping algorithm can sweep with something which is not a line.
- we use a sweeping ray going around $p$
- take polar coordinates $(r, \phi)$ with origin in $p$
- state: heap containing the segments intersecting the sweeping ray
- events: starting and ending points of segments
- output: set
- initialization:
- event queue: sort the endpoints of segments by $\phi$ into a sorted list ($O(n \log n)$)
- state: add the segments intersecting the sweeping ray in initial position $\phi = 0$ ($O(n \log n)$)
- events ($O(n)$):
- starting point:
- add the corresponding segment to the state ($O(\log n)$)
- if the new segment is first in the state, add it to the output ($O(1)$)
- ending point:
- remove the corresponding segment from the state ($O(\log n)$)
- if the segment was first in the state, add the new first segment to the output ($O(1)$)
- time complexity: $O(n \log n)$
Exercise 4
We are given a set $P$ of $n$ points in a plane, and two more points $q,q’ \notin P$. We are looking for the disk ${D_\min}$ which contains $q, q’$ and the least number of points from $P$.
- Prove: if there is a disk containing $q, q’$ and $k$ more points from $P$, then there exists a disk with $q, q’$ on its boundary which contains at most $k$ points of $P$.
- For a given point $p$, let $C(p)$ be the set of centers of the disks containing $p$ with $q, q’$ on their boundary. What is $C(p)$?
- Describe an algorithm which finds ${D_\min}$ in $O(n \log n)$ time.