Implicitly searching convolutions and computing depth of collision

David Paul Dobkin, John Hershberger, David Kirkpatrick, Subhash Suri

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

6 Scopus citations

Abstract

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
Pages165-180
Number of pages16
ISBN (Print)9783540529217
DOIs
StatePublished - Jan 1 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

Other

Other1st SIGAL International Symposium on Algorithms, 1990
CountryJapan
CityTokyo
Period8/16/908/18/90

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

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

  • Cite this

    Dobkin, D. P., Hershberger, J., Kirkpatrick, D., & Suri, S. (1990). Implicitly searching convolutions and computing depth of collision. In T. lbaraki, T. Nishizeki, H. Imai, & T. Asano (Eds.), Algorithms - International Symposium SlGAL 1990, Proceedings (pp. 165-180). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 450 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-52921-7_66