Primitives for the manipulation of three-dimensional subdivisions. (English) Zbl 0664.68023

Algorithms for manipulating three-dimensional cell complexes are seldom implemented due to the lack of a suitable data structure for representing them. Such a data structure is proposed here along with the primitive operations necessary to make it useful. Applications of the structure are also given.


68P05 Data structures
68U99 Computing methodologies and applications
52Bxx Polytopes and polyhedra
Full Text: DOI


[1] Avis, D.; Bhattacharya, B. K.; Preparata, F. P., Algorithms for computingd-dimensional Voronoi diagrams and their duals, Advances in Computing Research, vol. 1, 159-180 (1983), Greenwich, CT: JAI Press, Greenwich, CT
[2] B. G. Baumgart, A polyhedron representation for computer vision, in1975 National Computer Conference, AFIPS Conference Proceedings, vol. 44, AFIPS Press, 1976, pp. 589-596.
[3] B. K. Bhattacharya, Application of computational geometry to pattern recognition problems, Tech. Rep. 82-3, Simon Fraser University, 1982.
[4] Braid, I. C.; Hillyard, R. C.; Stroud, I. A.; Brodlie, K. W., Stepwise construction of polyhedra in geometric modelling, Mathematical Methods in Computer Graphics and Design, 123-141 (1980), London: Academic Press, London
[5] Brown, K. Q., Voronoi diagrams from convex hulls, Inform. Process. Lett., 9, 223-228 (1979) · Zbl 0424.68036 · doi:10.1016/0020-0190(79)90074-7
[6] B. Chazelle and D. P. Dobkin, Detection is easier than computation,Proc. 12th ACM SIGACT Symposium, Los Angeles, May 1980, pp. 146-153.
[7] Chand, D. R.; Kapur, S. S., An algorithm for convex polytopes, J. Assoc. Comput. Mach., 17, 1, 77-86 (1970) · Zbl 0199.50902
[8] C. M. Eastman and K. Weiler, Geometric modeling using the Euler operators, Research Rep. 78, Institute of Physical Planning, Carnegie-Mellon University, February 1979.
[9] Guibas, L.; Stolfi, J., Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams, ACM Trans. Graphics, 4, 2, 75-123 (1985) · Zbl 0586.68059 · doi:10.1145/282918.282923
[10] A. Jameson and T. Baker, Improvements to the aircraft Euler method, Paper AIAA-87-0452, AIAA 25th Aerospace Sciences Meeting, 1987.
[11] M. J. Laszlo, A data structure for manipulating three-dimensional subdivisions, Dissertation, Department of Computer Science, Princeton University, August 1987.
[12] B. Wördenweber, Volume-triangulation, C.A.D. Group, University of Cambridge, 1980.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.