Detection is easier than computation

Bernard Chazelle; David P. Dobkin

doi:10.1145/800141.804662

Detection is easier than computation

Bernard Chazelle, David P. Dobkin

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

43 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 language	English (US)
Title of host publication	Proceedings of the 12th Annual ACM Symposium on Theory of Computing, STOC 1980
Publisher	Association for Computing Machinery
Pages	146-153
Number of pages	8
ISBN (Electronic)	0897910176
DOIs	https://doi.org/10.1145/800141.804662
State	Published - Apr 28 1980
Event	12th Annual ACM Symposium on Theory of Computing, STOC 1980 - Los Angeles, United States Duration: Apr 28 1980 → Apr 30 1980

Publication series

Name	Proceedings of the Annual ACM Symposium on Theory of Computing
Volume	1980-April
ISSN (Print)	0737-8017

Other

Other	12th Annual ACM Symposium on Theory of Computing, STOC 1980
Country/Territory	United States
City	Los Angeles
Period	4/28/80 → 4/30/80

All Science Journal Classification (ASJC) codes

Software

Access to Document

10.1145/800141.804662

Cite this

@inproceedings{21b7a05ed4f64f3881b87ed5cb1a4b86,

title = "Detection is easier than computation",

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.",

author = "Bernard Chazelle and Dobkin, {David P.}",

note = "Publisher Copyright: {\textcopyright} 1980 ACM.; 12th Annual ACM Symposium on Theory of Computing, STOC 1980 ; Conference date: 28-04-1980 Through 30-04-1980",

year = "1980",

month = apr,

day = "28",

doi = "10.1145/800141.804662",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "146--153",

booktitle = "Proceedings of the 12th Annual ACM Symposium on Theory of Computing, STOC 1980",

}

Chazelle, B & Dobkin, DP 1980, Detection is easier than computation. in Proceedings of the 12th Annual ACM Symposium on Theory of Computing, STOC 1980. Proceedings of the Annual ACM Symposium on Theory of Computing, vol. 1980-April, Association for Computing Machinery, pp. 146-153, 12th Annual ACM Symposium on Theory of Computing, STOC 1980, Los Angeles, United States, 4/28/80. https://doi.org/10.1145/800141.804662

Detection is easier than computation. / Chazelle, Bernard; Dobkin, David P.
Proceedings of the 12th Annual ACM Symposium on Theory of Computing, STOC 1980. Association for Computing Machinery, 1980. p. 146-153 (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 1980-April).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Detection is easier than computation

AU - Chazelle, Bernard

AU - Dobkin, David P.

PY - 1980/4/28

Y1 - 1980/4/28

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84944046138&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84944046138&partnerID=8YFLogxK

U2 - 10.1145/800141.804662

DO - 10.1145/800141.804662

M3 - Conference contribution

AN - SCOPUS:84944046138

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 146

EP - 153

BT - Proceedings of the 12th Annual ACM Symposium on Theory of Computing, STOC 1980

PB - Association for Computing Machinery

T2 - 12th Annual ACM Symposium on Theory of Computing, STOC 1980

Y2 - 28 April 1980 through 30 April 1980

ER -

Detection is easier than computation

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this