DIMACS TR: 99-57
An Optimal Algorithm for Hyperplane Depth in the Plane
Authors: Stefan Langerman and William Steiger
ABSTRACT
Given a set of $n$ hyperplanes $h_1,\ldots,h_n \in R^d$ the
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$. We give an optimal $O(n\log{n})$ deterministic algorithm to
compute the hyperplane depth of an arrangement in dimension $d=2$.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-57.ps.gz
DIMACS Home Page