Proximate planar point location

John Iacono; Stefan Langerman

Proximate planar point location

John Iacono, Stefan Langerman

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

Abstract

A new data structure is presented for planar point location that executes a point location query quickly if it is spatially near the previous query. Given a triangulation T of size n and a sequence of point location queries A = q₁, . . . q_m, the structure presented executes q_i in time O(log d(q_i-1, q_i)). The distance function, d, that is used is a two dimensional generalization of rank distance that counts the number of triangles in a region from q_i-1 to q_i. The data structure uses O(n log log n) space.

Original language	English (US)
Title of host publication	Proceedings of the Annual Symposium on Computational Geometry
Pages	220-226
Number of pages	7
State	Published - 2003
Event	Nineteenth Annual Symposium on Computational Geometry - san Diego, CA, United States Duration: Jun 8 2003 → Jun 10 2003

Other

Other	Nineteenth Annual Symposium on Computational Geometry
Country/Territory	United States
City	san Diego, CA
Period	6/8/03 → 6/10/03

Keywords

Planar point location

ASJC Scopus subject areas

Chemical Health and Safety
Software
Safety, Risk, Reliability and Quality
Geometry and Topology

Cite this

@inproceedings{22930e94c5a84d43a571e8fb865ba251,

title = "Proximate planar point location",

abstract = "A new data structure is presented for planar point location that executes a point location query quickly if it is spatially near the previous query. Given a triangulation T of size n and a sequence of point location queries A = q1, . . . qm, the structure presented executes qi in time O(log d(qi-1, qi)). The distance function, d, that is used is a two dimensional generalization of rank distance that counts the number of triangles in a region from qi-1 to qi. The data structure uses O(n log log n) space.",

keywords = "Planar point location",

author = "John Iacono and Stefan Langerman",

year = "2003",

language = "English (US)",

pages = "220--226",

booktitle = "Proceedings of the Annual Symposium on Computational Geometry",

note = "Nineteenth Annual Symposium on Computational Geometry ; Conference date: 08-06-2003 Through 10-06-2003",

}

TY - GEN

T1 - Proximate planar point location

AU - Iacono, John

AU - Langerman, Stefan

PY - 2003

Y1 - 2003

N2 - A new data structure is presented for planar point location that executes a point location query quickly if it is spatially near the previous query. Given a triangulation T of size n and a sequence of point location queries A = q1, . . . qm, the structure presented executes qi in time O(log d(qi-1, qi)). The distance function, d, that is used is a two dimensional generalization of rank distance that counts the number of triangles in a region from qi-1 to qi. The data structure uses O(n log log n) space.

AB - A new data structure is presented for planar point location that executes a point location query quickly if it is spatially near the previous query. Given a triangulation T of size n and a sequence of point location queries A = q1, . . . qm, the structure presented executes qi in time O(log d(qi-1, qi)). The distance function, d, that is used is a two dimensional generalization of rank distance that counts the number of triangles in a region from qi-1 to qi. The data structure uses O(n log log n) space.

KW - Planar point location

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

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

M3 - Conference contribution

AN - SCOPUS:0038038272

SP - 220

EP - 226

BT - Proceedings of the Annual Symposium on Computational Geometry

T2 - Nineteenth Annual Symposium on Computational Geometry

Y2 - 8 June 2003 through 10 June 2003

ER -

Proximate planar point location

Abstract

Other

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this