Detection is easier than computation

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

42 Scopus citations

Abstract

Perhaps the most important application of computer geometry involves determining whether a pair of convex objects intersect. This problem is well understood in a model of computation where the objects are given as input and their intersection is returned as output. However, for many applications, we may assume that the objects already exist within the computer and that the only output desired is a single piece of data giving a common point if the objects intersect or reporting no intersection if they are disjoint. For this problem, none of the previous lower bounds are valid and we propose algorithms requiring sublinear time for their solution in 2 and 3 dimensions.

Original languageEnglish (US)
Title of host publicationProceedings of the 12th Annual ACM Symposium on Theory of Computing, STOC 1980
PublisherAssociation for Computing Machinery
Pages146-153
Number of pages8
ISBN (Electronic)0897910176
DOIs
StatePublished - Apr 28 1980
Externally publishedYes
Event12th Annual ACM Symposium on Theory of Computing, STOC 1980 - Los Angeles, United States
Duration: Apr 28 1980Apr 30 1980

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
Volume1980-April
ISSN (Print)0737-8017

Other

Other12th Annual ACM Symposium on Theory of Computing, STOC 1980
CountryUnited States
CityLos Angeles
Period4/28/804/30/80

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Detection is easier than computation'. Together they form a unique fingerprint.

  • Cite this

    Chazelle, B., & Dobkin, D. P. (1980). Detection is easier than computation. In Proceedings of the 12th Annual ACM Symposium on Theory of Computing, STOC 1980 (pp. 146-153). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 1980-April). Association for Computing Machinery. https://doi.org/10.1145/800141.804662