Better algorithm

Tools


Convex hull of vertices of a line arrangement

Definition: Convex set (source: lectures)
A set in Euclidean space $R^d$ is a convex set if it contains all the line segments connecting any pair of its points.
Definition: Convex Hull (source: lectures)
Given a set of points $S \subset R^d$, the convex hull $C$ of $S$ is defined as the intersection of all convex sets containing $S$.
More formally, \[ C = \{ \sum_{i = 1}^{\mid S \mid} \lambda_i x_i \mid (x_i \in S) \wedge (\forall i : \lambda_i \ge 0) \wedge \sum_{i = 1}^{\mid S \mid} \lambda_i = 1 \}\]

We need to construct the convex hull of vertices (line intersection) of a line arrangment $L$ of $n$ lines. We propose first the following combination of two algorithms to perform this task.

Algorithm: Proposition 1
  1. Find all intersections of the line arrangement $L$ ($S$ is the set of all these intersections) by the Bentley–Ottmann algorithm proposed in: Algorithms for Reporting and Counting Geometric Intersections
  2. Use Graham scan to compute the convex hull of the set of intersections $S$ found in (1) : An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set

The algorithm proposed here performs in $\mathcal{O}((n + \mid S \mid) \log n)$ time, due to the time complexity of the first step. Given that the number of intersections $\mid S \mid$ can possibly be $\mathcal{\Theta}(n^2)$, we should find an algorithm with better insurances.

Algorithm: Proposition 2
Based on the Bentley-Ottman, Esther M. Arkin, Joseph S. B. Mitchell, Jack Snoeyink introduced an algorithm finding the intersections of a line arrangement and building the corresponding convex hull in Capturing crossings: Convex hulls of segment and plane intersections
This algorithm constructs the convex hull of the set of vertices of a line arrangement $L$ of size $n$ in $\mathcal{O}( n \log n)$ time.

Dynamic convex hull

We know efficient algorithms to find the convex hull of a set of point $S$ such as Graham Scan. Sometime a Dynamic convex hull could be usefull in order to perform deletions and insertions of new points in $S$ efficiently. G.S.Brodal and R.Jacob described in their article Dynamic planar convex hull a data structure using $\mathcal{O}(n)$ space and insuring an amortized cost of $\mathcal{O}(\log n)$ time for deletion and insertion.



Insideness test

Definition: Insideness test
Given a convex polygon and $k$ the depth of the deepest point on the boundary of $P$. The insideness test consist in determining if the cell containing a depth greater than $k$ is inside or outside of $P$.

In The Complexity of Hyperplane Depth in the Plane writtent by Stefan Langerman and William Steiger, an algorithm allowing the insideness test defined above is described performing in $\mathcal{O}(m \log n +s)$.
The algorithm is based on the Wedge lemma and a data structure both defined in the article Efficient Algorithms for Maximum Regression Depth.



Sideness by insideness

Definition: Sideness test
Given a line $l$ and $k$ the depth of the deepest point on $l$, the sideness test consist in determining wich side of the plane split by $l$ does not contain any point with a greater depth than $k$.
Lemma: Sideness test by insideness
Suppose we have a line $l$, a convex polygon $P$ with $s$ sides, and a subset $U = \{1 ,...,m\} \subseteq S$ of the lines of $L$ that meet the interior of $P$. If $P$ contains a cell $C$ of maximal depth, then the sidedness test for $l$ can be performed in $\mathcal{O}(m \log n + s)$.

We define $P^+$ as the part of $P$ wich is above $l$. By performing the insideness (in $\mathcal{O}(m \log n + s)$ time) test on $P^+$, we can then decide if the cell with the greatest depth is above or below the line $l$.


Algorithm

We know describe an algorithm allowing to find a point with the greatest regression depth (dual space) in $\mathcal{O}(n \log n)$ time.


Algorithm: Deepest regression point (dual space)
PRUNE($U, Q, P$):
  • Input:
    • $U$ a set of unpruned lines
    • $Q$ a set of pruned lines
    • $P$ a convex polygon containing a cell of maximal depth
  • Steps:
    • Tant que $\mid U \mid > c$:
      1. choose a line $l \in U$ at random
      2. perform the sideness test for $l$
      3. Given the set $G = \{ l \cap l_i \mid l_i \in U \}$, choose nine vertical lines ($a_1, a_2, ..., a_9$) such that at most $m/9$ elements of $G$ lay in between $[a_i, a_{i+1}]$ pour tout $i$
      4. Side any vertical line $a_i$ to find the interval $[a_i, a_{i+1}]$ containing the point $\mu$ with the greatest depth
      5. Find $X$ the set of lines that intersects the vertical lines $a_i$ and $a_{i+1}$ found at the previous step on the side of $l$ not countaining $\mu$ and intesecting $l$ outside the interval $[a_i, a_{i+1}]$
      6. $U = U \backslash X$, $Q = Q \cup X$ and $P$ is updated by a dynamic convex algorithm (deleting vertices of the arrangement
    • For each line $\in U$: perform the sideness test and update $P$
    • Return a point $\mu \in P$
  • Initialization:
    • $U$ contains all lines $\in L$
    • $Q$ is empty
    • $P$ is a convex polygon containing big enough to contain all intersections of lines $\in L$