Document Open Access Logo

A Simpler Linear-Time Algorithm for Intersecting Two Convex Polyhedra in Three Dimensions

Author Timothy M. Chan

PDF
Thumbnail PDF

File

LIPIcs.SOCG.2015.733.pdf
  • Filesize: 338 kB
  • 6 pages

Document Identifiers

Author Details

Timothy M. Chan

Cite As Get BibTex

Timothy M. Chan. A Simpler Linear-Time Algorithm for Intersecting Two Convex Polyhedra in Three Dimensions. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 733-738, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.SOCG.2015.733

Abstract

Chazelle [FOCS'89] gave a linear-time algorithm to compute the intersection of two convex polyhedra in three dimensions. We present a simpler algorithm to do the same.

Subject Classification

Keywords
  • convex polyhedra
  • intersection
  • Dobkin–Kirkpatrick hierarchy

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Nancy M. Amato, Michael T. Goodrich, and Edgar A. Ramos. A randomized algorithm for triangulating a simple polygon in linear time. Discrete and Computational Geometry, 26(2):245-265, 2001. Google Scholar
  2. Timothy M. Chan. Deterministic algorithms for 2-d convex programming and 3-d online linear programming. Journal of Algorithms, 27(1):147-166, 1998. Google Scholar
  3. Bernard Chazelle. Triangulating a simple polygon in linear time. Discrete and Computational Geometry, 6:485-524, 1991. Google Scholar
  4. Bernard Chazelle. An optimal algorithm for intersecting three-dimensional convex polyhedra. SIAM Journal on Computing, 21(4):671-696, 1992. Google Scholar
  5. Kenneth L. Clarkson and Peter W. Shor. Application of random sampling in computational geometry, II. Discrete and Computational Geometry, 4:387-421, 1989. Google Scholar
  6. David P. Dobkin and David G. Kirkpatrick. A linear algorithm for determining the separation of convex polyhedra. Journal of Algorithms, 6(3):381-392, 1985. Google Scholar
  7. David P. Dobkin and David G. Kirkpatrick. Determining the separation of preprocessed polyhedra - A unified approach. In Proceedings of the 17th International Colloquium on Automata, Languages and Programming, pages 400-413, 1990. Google Scholar
  8. Martin E. Dyer, Nimrod Megiddo, and Emo Welzl. Linear programming. In Jacob E. Goodman and Joseph O'Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 45. CRC Press, second edition, 2004. Google Scholar
  9. David G. Kirkpatrick. Efficient computation of continuous skeletons. In Proceedings of the 20th Annual Symposium on Foundations of Computer Science, pages 18-27, 1979. Google Scholar
  10. David G. Kirkpatrick. Optimal search in planar subdivisions. SIAM Journal on Computing, 12(1):28-35, 1983. Google Scholar
  11. Andrew K. Martin. A simple primal algorithm for intersecting 3-polyhedra in linear time. Master’s thesis, Department of Computer Science, University of British Columbia, 1991. https://circle.ubc.ca/handle/2429/30114 or http://www.cs.ubc.ca/cgi-bin/tr/1991/TR-91-16. Google Scholar
  12. Ketan Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ, 1993. Google Scholar
  13. Franco P. Preparata and S. J. Hong. Convex hulls of finite sets of points in two and three dimensions. Communications of the ACM, 20(2):87-93, 1977. Google Scholar
  14. Michael Ian Shamos and Dan Hoey. Closest-point problems. In Proceedings of the 16th Annual Symposium on Foundations of Computer Science, pages 151-162, 1975. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact