On Finding Ordinary or Monochromatic Intersection Points

Abstract

An algorithm is demonstrated that finds an ordinary intersection in an arrangement of $n$ lines in ${\mathbb{R}}^2$, not all parallel and not all passing through a common point, in time $O(n\log n)$. The algorithm is then extended to find an ordinary intersection among an arrangement of hyperplanes in ${\mathbb{R}}^d$, no $d$ passing through a line and not all passing through the same point, again, in time $O(n\log n)$. Two additional algorithms are provided that find an ordinary or monochromatic intersection, respectively, in an arrangement of pseudolines in time $O(n^2)$.

21 pages, 4 figures