DIMACS TR: 99-57

An Optimal Algorithm for Hyperplane Depth in the Plane

Authors: Stefan Langerman and William Steiger


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