Arrangements of lines in 3-space: a data structure with applications
M. McKenna, Joseph O’Rourke · 1988
Let an arrangement of blue lines in 3-space be fixed, and imagine a movable red line entangled in the arrangement. We show an Ο(n4α(n)) algorithm for building a data structure that permits enumeration of mutually inaccessible classes of such red lines, where α(n) is the inverse Ackermann function. The core of the algorithm is a construction of Ο(n2) 2-D arrangement of hyperbolas, each in Ο(n2α(n)) time.The algorithm is applied to stabbing 3-polytopes, enumerating pairwise-visible face pairs, enumerating 2-D projections of convex 4-polytopes, and other problems, resulting in Ο(n4α(n)) algorithms in each case.