Computational Geometry

« 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.



Exercise 2

Let $P$ and $Q$ be $x$-monotonous paths with $n$ and $m$ vertices, respectively. Assume that no $3$ vertices are collinear.

  1. Prove that $P \cap Q$ has cardinality at most $O(n+m)$.
  2. 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.



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$.

  1. 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$.
  2. 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)$?
  3. Describe an algorithm which finds ${D_\min}$ in $O(n \log n)$ time.