Detection is easier than computation

Bernard Chazelle, David P. Dobkin

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

43 Scopus citations


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
Number of pages8
ISBN (Electronic)0897910176
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
ISSN (Print)0737-8017


Other12th Annual ACM Symposium on Theory of Computing, STOC 1980
Country/TerritoryUnited States
CityLos Angeles

All Science Journal Classification (ASJC) codes

  • Software


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

Cite this