On Finding Ordinary or Monochromatic Intersection Points

2009/10/01 by George B. Purdy, Purdy, George B., Justin W. Smith +1
Computer Science · #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #I.3.5 #cs.CG #cs.DM

paper · pdf · doi:10.48550/arxiv.0910.0286

21 pages, 4 figures

arxiv created 2009/10/01 · arxiv updated 2009/12/01

Abstract

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

Related

• A Simple Algorithm for Computing the Zone of a Line in an Arrangement of Lines
• A greedy algorithm to compute arrangements of lines in the projective plane
• Computation of the Hausdorff distance between sets of line segments in parallel
• A note on coloring line arrangements
• Parsimonious Simplicial Intersection Algorithm