Expected asymptotically optimal planar point location

John Iacono

doi:10.1016/j.comgeo.2004.03.010

Expected asymptotically optimal planar point location

John Iacono

Research output: Contribution to journal › Article › peer-review

Abstract

Given a fixed distribution of point location queries among the triangles in a triangulation of the plane, a data structure is presented that achieves, within constant multiplicative factors, the entropy bound on the expected point location query time. The data structure is a simple variation of Kirkpatrick's classic planar point location structure [D.G. Kirkpatrick, SIAM J. Comput. 12 (1) (1983) 28-35], and has linear construction costs and space requirements.

Original language	English (US)
Pages (from-to)	19-22
Number of pages	4
Journal	Computational Geometry: Theory and Applications
Volume	29
Issue number	1
DOIs	https://doi.org/10.1016/j.comgeo.2004.03.010
State	Published - Sep 2004

Keywords

Distribution-sensitive data structures
Point location

ASJC Scopus subject areas

Computer Science Applications
Geometry and Topology
Control and Optimization
Computational Theory and Mathematics
Computational Mathematics

Access to Document

10.1016/j.comgeo.2004.03.010

Cite this

@article{8b09e3f591314fd4a188a872647dde00,

title = "Expected asymptotically optimal planar point location",

abstract = "Given a fixed distribution of point location queries among the triangles in a triangulation of the plane, a data structure is presented that achieves, within constant multiplicative factors, the entropy bound on the expected point location query time. The data structure is a simple variation of Kirkpatrick's classic planar point location structure [D.G. Kirkpatrick, SIAM J. Comput. 12 (1) (1983) 28-35], and has linear construction costs and space requirements.",

keywords = "Distribution-sensitive data structures, Point location",

author = "John Iacono",

note = "Funding Information: 1 Part of this work was done while the author was at Rutgers, The State University of New Jersey–New Brunswick. Research partially supported by NSF grant CCR-9732689.",

year = "2004",

month = sep,

doi = "10.1016/j.comgeo.2004.03.010",

language = "English (US)",

volume = "29",

pages = "19--22",

journal = "Computational Geometry: Theory and Applications",

issn = "0925-7721",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - Expected asymptotically optimal planar point location

AU - Iacono, John

N1 - Funding Information: 1 Part of this work was done while the author was at Rutgers, The State University of New Jersey–New Brunswick. Research partially supported by NSF grant CCR-9732689.

PY - 2004/9

Y1 - 2004/9

N2 - Given a fixed distribution of point location queries among the triangles in a triangulation of the plane, a data structure is presented that achieves, within constant multiplicative factors, the entropy bound on the expected point location query time. The data structure is a simple variation of Kirkpatrick's classic planar point location structure [D.G. Kirkpatrick, SIAM J. Comput. 12 (1) (1983) 28-35], and has linear construction costs and space requirements.

AB - Given a fixed distribution of point location queries among the triangles in a triangulation of the plane, a data structure is presented that achieves, within constant multiplicative factors, the entropy bound on the expected point location query time. The data structure is a simple variation of Kirkpatrick's classic planar point location structure [D.G. Kirkpatrick, SIAM J. Comput. 12 (1) (1983) 28-35], and has linear construction costs and space requirements.

KW - Distribution-sensitive data structures

KW - Point location

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

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

U2 - 10.1016/j.comgeo.2004.03.010

DO - 10.1016/j.comgeo.2004.03.010

M3 - Article

AN - SCOPUS:77952708241

SN - 0925-7721

VL - 29

SP - 19

EP - 22

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

IS - 1

ER -

Expected asymptotically optimal planar point location

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this