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 \}\]

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

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

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.

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.

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

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)

**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$:
- choose a line $l \in U$ at random
- perform the sideness test for $l$
- 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$
- Side any vertical line $a_i$ to find the interval $[a_i, a_{i+1}]$ containing the point $\mu$ with the greatest depth
- 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}]$
- $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$

- Tant que $\mid U \mid > c$:
**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$