Storing the subdivision of a polyhedral surface

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 pointx on the surface of the polyhedron, the region of the subdivision containingx can be determined in logarithmic time. Ifn denotes the number of edges in the polyhedron,m denotes the number of geodesics in the subdivision, andK denotes the number of intersections between edges and geodesics, then the space required by the data structure isO((n +m) log(n +m)), and the structure can be built inO(K + (n +m) log(n +m)) time. 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.