An acyclicity theorem for cell complexes in d dimensions

ABSTRACT

Let C be a cell complex in d-dimensional Euclidean space whose faces are obtained by orthogonal projection of the faces of a convex polytope in d + 1 dimensions. For example, the Delaunay triangulation of a finite point set is such a cell complex. This paper shows that the in_front/behind relation defined for the faces of C with respect to any fixed viewpoint x is acyclic. This result has applications to hidden line/surface removal and other problems in computational geometry.

REFERENCES

• 1: F Aurenhammer, Power diagrams: properties, algorithms and applications, SIAM Journal on Computing, v.16 n.1, p.78-96, Feb. 1987 [doi>10.1137/0216006]
• 2: Bernard Chazelle, How to search history, Information and Control, v.64 n.1-3, p.77-99, Jan./Feb./March 1985 [doi>10.1016/S0019-9958(85)80045-0]
• 3: B. Delaunay. Sur la sphhre vide. Izu. Akad. Nuuk SSSR, Otdelenie. Matemalicheakii i Eatestvennyka Nuuk 7 (1934), 793-800.
• 4: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 5: H. Edelsbrunner, D. G. Kirkpatrick and R. Seidel. On the shape of a set of points in the plane. IEEE Bans. Inform. Theory IT-29 (1983), 551- 559.
• 6: L. De Floriani, B. Falcidieno, C. Pienovi, and G. Nagy. On sorting triangles in a Delaunay tessellation. Techn. Rept., Instituto per la Matematica Applicata, Consiglio Nazionale delle Richerche, Genova, Italy, 1988.
• 7: James D. Foley , Andries Van Dam, Fundamentals of interactive computer graphics, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
• 8: Henry Fuchs , Zvi M. Kedem , Bruce F. Naylor, On visible surface generation by a priori tree structures, Proceedings of the 7th annual conference on Computer graphics and interactive techniques, p.124-133, July 14-18, 1980, Seattle, Washington, United States
• 9: G. Voronoi. Sur quelques propriktCs des formes quadratiques parfaites. J. Reine Angew. Math. 133 (1907), 212-287.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional 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.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

General Terms:
Algorithms, Theory