Storing the subdivision of a polyhedral surface (Q1820438)

Let P be a polyhedron, composed of a finite number of vertices, n (say) edges, and convex polygonal faces in 3-space, and suppose P simply- connected (although this condition can be relaxed a little). Let P be subdivided by a graph Q consisting of a finite number m (say) of geodesics on P, and suppose that there are K intersections between edges of P and geodesics of Q. The author constructs an algorithm which represents the subdivision in space \(O((n+m)\log (n+m)),\) and can be built in time \(O(K+(n+m)\log (n+m)).\) This enables various queries about the subdivision (for example, to which region a given point belongs) to be answered efficiently.