COCOA Talk: 2000-01

Speaker: Stefan Langerman

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