Optimal planar point location

John Iacono

Optimal planar point location

John Iacono

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

Abstract

Given a fixed distribution of point location queries among the regions of 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.

Original language	English (US)
Title of host publication	Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms
Pages	340-341
Number of pages	2
State	Published - 2001
Event	2001 Operating Section Proceedings, American Gas Association - Dallas, TX, United States Duration: Apr 30 2001 → May 1 2001

Publication series

Name	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other	2001 Operating Section Proceedings, American Gas Association
Country/Territory	United States
City	Dallas, TX
Period	4/30/01 → 5/1/01

Keywords

Algorithms
Theory

ASJC Scopus subject areas

Software
General Mathematics

Cite this

@inproceedings{3ea99c72a0db4407a57c4d0052b91e00,

title = "Optimal planar point location",

abstract = "Given a fixed distribution of point location queries among the regions of 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.",

keywords = "Algorithms, Theory",

author = "John Iacono",

year = "2001",

language = "English (US)",

isbn = "0898714907",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

pages = "340--341",

booktitle = "Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms",

note = "2001 Operating Section Proceedings, American Gas Association ; Conference date: 30-04-2001 Through 01-05-2001",

}

TY - GEN

T1 - Optimal planar point location

AU - Iacono, John

PY - 2001

Y1 - 2001

N2 - Given a fixed distribution of point location queries among the regions of 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.

AB - Given a fixed distribution of point location queries among the regions of 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.

KW - Algorithms

KW - Theory

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

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

M3 - Conference contribution

AN - SCOPUS:64049091682

SN - 0898714907

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 340

EP - 341

BT - Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms

T2 - 2001 Operating Section Proceedings, American Gas Association

Y2 - 30 April 2001 through 1 May 2001

ER -

Optimal planar point location

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this