## COCOA Talk: 2000-01

## An Optimal Algorithm for Hyperplane Depth in the Plane

### Speaker: Stefan Langerman

**
ABSTRACT
**

Given a set of $n$ hyperplanes $h_1,\ldots,h_n \in R^d$ the {\em
hyperplane depth} of a point $P\in R^d$ is the minimum number of
hyperplanes that a ray from $P$ can meet. The {\em hyperplane depth}
of the arrangement is the maximal depth of points $P$ not in any
$h_i$. I will present an optimal $O(n\log{n})$ deterministic algorithm to
compute the hyperplane depth of an arrangement in dimension $d=2$.

DIMACS Home Page