Implicitly searching convolutions and computing depth of collision

David Dobkin, John Hershberger, David Kirkpatrick, Subhash Suri

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

7 Scopus citations


Given two intersecting polyhedra P, Q and a direction d, find the smallest translation of Q along d that renders the interiors of P and Q disjoint. The same question can also be asked without specifying the direction, in which case the minimum translation over all directions is sought. These are fundamental problems that arise in robotics and computer vision. We develop techniques for implicitly building and searching convolutions and apply them to derive efficient algorithms for these problems.

Original languageEnglish (US)
Title of host publicationAlgorithms - International Symposium SlGAL 1990, Proceedings
EditorsToshihide lbaraki, Takao Nishizeki, Hiroshi Imai, Tetsuo Asano
PublisherSpringer Verlag
Number of pages16
ISBN (Print)9783540529217
StatePublished - 1990
Event1st SIGAL International Symposium on Algorithms, 1990 - Tokyo, Japan
Duration: Aug 16 1990Aug 18 1990

Publication series

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


Other1st SIGAL International Symposium on Algorithms, 1990

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Implicitly searching convolutions and computing depth of collision'. Together they form a unique fingerprint.

Cite this