Geometric searching over the rationals

Research output: Chapter in Book/Report/Conference proceedingConference 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 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?.

Original languageEnglish (US)
Title of host publicationAlgorithms - ESA 1999 - 7th Annual European Symposium, Proceedings
EditorsJaroslav Nešetřil
PublisherSpringer Verlag
Pages354-365
Number of pages12
ISBN (Print)3540662510, 9783540662518
DOIs
StatePublished - 1999
Event7th Annual European Symposium on Algorithms, ESA 1999 - Prague, Czech Republic
Duration: Jul 16 1999Jul 18 1999

Publication series

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

Other

Other7th Annual European Symposium on Algorithms, ESA 1999
Country/TerritoryCzech Republic
CityPrague
Period7/16/997/18/99

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Geometric searching over the rationals'. Together they form a unique fingerprint.

Cite this