Fast detection of polyhedral intersections

David Paul Dobkin, David G. Kirkpatrick

Research output: Chapter in Book/Report/Conference proceedingConference contribution

22 Scopus citations

Abstract

Methods are given for unifying and extending previous work on detecting polyhedral intersections. The technique of dynamic (vs. static) description is introduced and used to extend previous results. New upper bounds of O(log n) and O(log 2 n) are given on plane-polyhedron and polyhedron-polyhedron intersection problems.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 9th Colloquium
EditorsMogens Nielsen, Erik Meineche Schmidt
PublisherSpringer Verlag
Pages154-165
Number of pages12
ISBN (Print)9783540115762
DOIs
StatePublished - Jan 1 1982
Event9th International Colloquium on Automata, Languages and Programming, ICALP 1982 - Aarhus, Denmark
Duration: Jul 12 1982Jul 16 1982

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume140 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other9th International Colloquium on Automata, Languages and Programming, ICALP 1982
CountryDenmark
CityAarhus
Period7/12/827/16/82

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Fast detection of polyhedral intersections'. Together they form a unique fingerprint.

  • Cite this

    Dobkin, D. P., & Kirkpatrick, D. G. (1982). Fast detection of polyhedral intersections. In M. Nielsen, & E. M. Schmidt (Eds.), Automata, Languages and Programming - 9th Colloquium (pp. 154-165). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 140 LNCS). Springer Verlag. https://doi.org/10.1007/BFb0012765