Skip to main content
SpringerLink
Log in

Primitives for the manipulation of three-dimensional subdivisions

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. D. Avis and B. K. Bhattacharya, Algorithms for computingd-dimensional Voronoi diagrams and their duals, inAdvances in Computing Research, vol. 1, F. P. Preparata, ed., JAI Press, Greenwich, CT, 1983, pp. 159–180.

    Google Scholar 

  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. I. C. Braid, R. C. Hillyard, and I. A. Stroud, Stepwise construction of polyhedra in geometric modelling, inMathematical Methods in Computer Graphics and Design, K. W. Brodlie, ed., Academic Press, London, 1980, pp. 123–141.

    Google Scholar 

  5. K. Q. Brown, Voronoi diagrams from convex hulls,Inform. Process. Lett.,9, 1979, 223–228.

    Article  MATH  Google Scholar 

  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. D. R. Chand and S. S. Kapur, An algorithm for convex polytopes,J. Assoc. Comput. Mach.,17(1), 1970, 77–86.

    MathSciNet  Google Scholar 

  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. L. Guibas and J. Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams,ACM Trans. Graphics,4(2), 1985, 75–123.

    Article  Google Scholar 

  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.

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Princeton University, 08544, Princeton, NJ, USA

    David P. Dobkin

  2. Department of Electrical Engineering and Computer Science, University of Illinois at Chicago, 60680, Chicago, ILL, USA

    Michael J. Laszlo

Authors
  1. David P. Dobkin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Michael J. Laszlo
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by Chee-Keng Yap.

This work was supported in part by the National Science Foundation under Grant No. DCR85-05517.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Dobkin, D.P., Laszlo, M.J. Primitives for the manipulation of three-dimensional subdivisions. Algorithmica 4, 3–32 (1989). https://doi.org/10.1007/BF01553877

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01553877

Key words

Search

Navigation