Storing the subdivision of a polyhedral surface
David M. Mount · 1986
A common structure arising in computational geometry is the subdivision of a plane defined by the faces of a straight line planar graph. We consider a natural generalization of this structure on a polyhedral surface. The regions of the subdivision are bounded by geodesics on the surface of the polyhedron. A method is given for representing such a subdivision that is efficient both with respect to space and the time required to answer a number of different queries involving the subdivision. For example, given a point @@@@ on the surface of the polyhedron, the region of the subdivision containing x can be determined in logarithmic time. If n denotes the number of edges in the polyhedron, and m denotes the number of geodesics in the subdivision, then the space required by the data structure is Ο((n + m) log (n + m)). Combined with existing algorithms for computing Voronoi diagrams on the surface of polyhedra, this structure provides an efficient solution to the nearest neighbor query problem on polyhedral surfaces.