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 -