Determining the separation of preprocessed polyhedra — A unified approach

David P. Dobkin, David G. Kirkpatrick

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

130 Scopus citations

Abstract

We show how (now familiar) hierarchical representations of (convex) polyhedra can be used to answer various separation queries efficiently (in a number of cases, optimally). Our emphasis is i) the uniform treatment of polyhedra separation problems, ii) the use of hierarchical representations of primitive objects to provide implicit representations of composite or transformed objects, and iii) applications to natural problems in graphics and robotics. Among the specific results is an O(log|P|·log|Q|) algorithm for determining the separation of polyhedra P and Q (which have been individually preprocessed in at most linear time).

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - l7th International Colloquium, Proceedings
EditorsMichael S. Paterson
PublisherSpringer Verlag
Pages400-413
Number of pages14
ISBN (Print)9783540528265
DOIs
StatePublished - Jan 1 1990
Event17th International Colloquium on Automata, Languages and Programming, 1990 - Warwick, United Kingdom
Duration: Jul 16 1990Jul 20 1990

Publication series

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

Other

Other17th International Colloquium on Automata, Languages and Programming, 1990
CountryUnited Kingdom
CityWarwick
Period7/16/907/20/90

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Determining the separation of preprocessed polyhedra — A unified approach'. Together they form a unique fingerprint.

  • Cite this

    Dobkin, D. P., & Kirkpatrick, D. G. (1990). Determining the separation of preprocessed polyhedra — A unified approach. In M. S. Paterson (Ed.), Automata, Languages and Programming - l7th International Colloquium, Proceedings (pp. 400-413). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 443 LNCS). Springer Verlag. https://doi.org/10.1007/bfb0032047