@inproceedings{adea4c3a5917470ba50cd3c4da615cce,
title = "Determining the separation of preprocessed polyhedra — A unified approach",
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).",
author = "Dobkin, {David P.} and Kirkpatrick, {David G.}",
note = "Funding Information: One of the essentied themes of our earlier work (including also [19]) has been the introduction and exploitation of hierarchical representations of polytopes in this setting. In [9] two (essentially dual) hierarchical representations for (convex) polygons and polyhedra were introduced and some of their basic properties (such as the efficient response to extremal queries) *Supported in part by NSF Grant Number CCR87-00917 and a Guggenheim Fellowship. tSupported in paxt by Natural Sciences and Engineering Research Council Grant A3583 and a BCASI Fellowship. Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1990.; 17th International Colloquium on Automata, Languages and Programming, 1990 ; Conference date: 16-07-1990 Through 20-07-1990",
year = "1990",
doi = "10.1007/bfb0032047",
language = "English (US)",
isbn = "9783540528265",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "400--413",
editor = "Paterson, {Michael S.}",
booktitle = "Automata, Languages and Programming - l7th International Colloquium, Proceedings",
address = "Germany",
}