On Finding Ordinary Intersection Points
George Purdy, Justin W. Smith · 2009
An algorithm is demonstrated that finds an ordinary intersection in an arrangement of n lines in R², 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 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²).