Geometric searching over the rationals

Bernard Chazelle

doi:10.1007/3-540-48481-7_31

Geometric searching over the rationals

Bernard Chazelle

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

2 Scopus citations

Abstract

We revisit classical geometric search problems under the assumption of rational coordinates. Our main result is a tight bound for point separation, ie, to determine whether n given points lie on one side of a query line. We show that with polynomial storage the query time is Θ(log b/ log log b), where b is the bit length of the rationals used in specifying the line and the points. The lower bound holds in Yao's cell probe model with storage in n^O(1) and word size in b^O(1).By duality, this provides a tight lower bound on the complexity on the polygon point enclosure problem: given a polygon in the plane, is a query point in it?.

Original language	English (US)
Title of host publication	Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings
Editors	Jaroslav Nešetřil
Publisher	Springer Verlag
Pages	354-365
Number of pages	12
ISBN (Print)	3540662510, 9783540662518
DOIs	https://doi.org/10.1007/3-540-48481-7_31
State	Published - 1999
Event	7th Annual European Symposium on Algorithms, ESA 1999 - Prague, Czech Republic Duration: Jul 16 1999 → Jul 18 1999

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1643
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	7th Annual European Symposium on Algorithms, ESA 1999
Country/Territory	Czech Republic
City	Prague
Period	7/16/99 → 7/18/99

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/3-540-48481-7_31

Cite this

Chazelle, B. (1999). Geometric searching over the rationals. In J. Nešetřil (Ed.), Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings (pp. 354-365). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1643). Springer Verlag. https://doi.org/10.1007/3-540-48481-7_31

@inproceedings{790c3709518e48baac2a69be222dc549,

title = "Geometric searching over the rationals",

abstract = "We revisit classical geometric search problems under the assumption of rational coordinates. Our main result is a tight bound for point separation, ie, to determine whether n given points lie on one side of a query line. We show that with polynomial storage the query time is Θ(log b/ log log b), where b is the bit length of the rationals used in specifying the line and the points. The lower bound holds in Yao's cell probe model with storage in nO(1) and word size in bO(1).By duality, this provides a tight lower bound on the complexity on the polygon point enclosure problem: given a polygon in the plane, is a query point in it?.",

author = "Bernard Chazelle",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1999.; 7th Annual European Symposium on Algorithms, ESA 1999 ; Conference date: 16-07-1999 Through 18-07-1999",

year = "1999",

doi = "10.1007/3-540-48481-7_31",

language = "English (US)",

isbn = "3540662510",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "354--365",

editor = "Jaroslav Ne{\v s}et{\v r}il",

booktitle = "Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings",

address = "Germany",

}

Chazelle, B 1999, Geometric searching over the rationals. in J Nešetřil (ed.), Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1643, Springer Verlag, pp. 354-365, 7th Annual European Symposium on Algorithms, ESA 1999, Prague, Czech Republic, 7/16/99. https://doi.org/10.1007/3-540-48481-7_31

Geometric searching over the rationals. / Chazelle, Bernard.
Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings. ed. / Jaroslav Nešetřil. Springer Verlag, 1999. p. 354-365 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1643).

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

TY - GEN

T1 - Geometric searching over the rationals

AU - Chazelle, Bernard

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1999.

PY - 1999

Y1 - 1999

N2 - We revisit classical geometric search problems under the assumption of rational coordinates. Our main result is a tight bound for point separation, ie, to determine whether n given points lie on one side of a query line. We show that with polynomial storage the query time is Θ(log b/ log log b), where b is the bit length of the rationals used in specifying the line and the points. The lower bound holds in Yao's cell probe model with storage in nO(1) and word size in bO(1).By duality, this provides a tight lower bound on the complexity on the polygon point enclosure problem: given a polygon in the plane, is a query point in it?.

AB - We revisit classical geometric search problems under the assumption of rational coordinates. Our main result is a tight bound for point separation, ie, to determine whether n given points lie on one side of a query line. We show that with polynomial storage the query time is Θ(log b/ log log b), where b is the bit length of the rationals used in specifying the line and the points. The lower bound holds in Yao's cell probe model with storage in nO(1) and word size in bO(1).By duality, this provides a tight lower bound on the complexity on the polygon point enclosure problem: given a polygon in the plane, is a query point in it?.

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

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

U2 - 10.1007/3-540-48481-7_31

DO - 10.1007/3-540-48481-7_31

M3 - Conference contribution

AN - SCOPUS:84958059433

SN - 3540662510

SN - 9783540662518

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 354

EP - 365

BT - Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings

A2 - Nešetřil, Jaroslav

PB - Springer Verlag

T2 - 7th Annual European Symposium on Algorithms, ESA 1999

Y2 - 16 July 1999 through 18 July 1999

ER -

Geometric searching over the rationals

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this