Storing the subdivision of a polyhedral surface

ABSTRACT

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 &Ogr;((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.

REFERENCES

• 1: D. Dobkin and D. Kirkpatrick, Fast Detection of Polyhedral Intersections, Theoretical Computer Science, 27, 241-253 (1983).
• 2: D. P. Dobkin and J. I. Munro, Efficient Uses of the Past, Journal of Algorithms, 6, 455-465 (1985).
• 3: Herbert Edelsbrunner , Lionidas J Guibas , Jorge Stolfi, Optimal point location in a monotone subdivision, SIAM Journal on Computing, v.15 n.2, p.317-340, May 1986 [doi>10.1137/0215023]
• 4: Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
• 5: D. G. Kirkpatrick, Optimal Search in Planar Subdivisions, SIAM, J. Comput. 12, 28-35 (1983).
• 6: D. T. Lee and F. P. Preparata, Location of a Point in a Planar Subdivision and its Applications, SIAM J. Comput., 6, 595-606 (1977).
• 7: Joseph S. B. Mitchell , David M. Mount , Christos H. Papadimitriou, The discrete geodesic problem, SIAM Journal on Computing, v.16 n.4, p.647-668, Aug. 1987 [doi>10.1137/0216045]
• 8: D. M. Mount, On Finding Shortest Paths on Convex Polyhedra, Univ. of Maryland, Tech. Rept. 1495 (1985).
• 9: D. M. Mount, Voronoi Diagrams on the Surface of a Polyhedron, Univ. of Maryland, Tech. Rept. 1496 (1985).
• 10: D: E. Muller and F. P. Preparata, Finding the intersection of Two Convex Polyhedra, Theor. Comput. Sci. 7,217-236 (1978).
• 11: F. P. Preparata, A New Approach to Planar Point Location, SIAM J. Comput., 10, 473-482 (1981).
• 12: M. I. Shamos and D. Hoey, Closest-Point Problems, Proc. of the 16th IEEE FOCS Symposium, 151-162 (1975).
• 13: Micha Sharir( , Amir Schorr, On shortest paths in polyhedral spaces, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.144-153, December 1984 [doi>10.1145/800057.808676]
• 14: M. Sharir, Intersection and Closest-pair Problems for a Set of Planar Discs, SIAM J. Comput., 14, 448-468, (1985).

INDEX TERMS

Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.6 Segmentation
          Subjects: Region growing, partitioning

General Terms:
Algorithms, Performance, Theory, Verification