Distribution-sensitive point location in convex subdivisions

Sébastien Collette; Vida Dujmović; John Iacono; Stefan Langerman; Pat Morin

Distribution-sensitive point location in convex subdivisions

Sébastien Collette, Vida Dujmović, John Iacono, Stefan Langerman, Pat Morin

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

Abstract

A data structure is presented for point location in convex planar subdivisions when the distribution of queries is known in advance. The data structure has an expected query time that differs from the optimal one by only lower order terms in the linear comparison tree model.

Original language	English (US)
Title of host publication	Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms
Pages	912-921
Number of pages	10
State	Published - 2008
Event	19th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, United States Duration: Jan 20 2008 → Jan 22 2008

Publication series

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

Other

Other	19th Annual ACM-SIAM Symposium on Discrete Algorithms
Country/Territory	United States
City	San Francisco, CA
Period	1/20/08 → 1/22/08

ASJC Scopus subject areas

Software
General Mathematics

Cite this

Distribution-sensitive point location in convex subdivisions. / Collette, Sébastien; Dujmović, Vida; Iacono, John et al.
Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. 2008. p. 912-921 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

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

Collette, S, Dujmović, V, Iacono, J, Langerman, S & Morin, P 2008, Distribution-sensitive point location in convex subdivisions. in Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 912-921, 19th Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, United States, 1/20/08.

@inproceedings{ec255b7ac6f04545a7aa8f4e68baefcd,

title = "Distribution-sensitive point location in convex subdivisions",

abstract = "A data structure is presented for point location in convex planar subdivisions when the distribution of queries is known in advance. The data structure has an expected query time that differs from the optimal one by only lower order terms in the linear comparison tree model.",

author = "S{\'e}bastien Collette and Vida Dujmovi{\'c} and John Iacono and Stefan Langerman and Pat Morin",

year = "2008",

language = "English (US)",

isbn = "9780898716474",

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

pages = "912--921",

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

note = "19th Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 20-01-2008 Through 22-01-2008",

}

TY - GEN

T1 - Distribution-sensitive point location in convex subdivisions

AU - Collette, Sébastien

AU - Dujmović, Vida

AU - Iacono, John

AU - Langerman, Stefan

AU - Morin, Pat

PY - 2008

Y1 - 2008

N2 - A data structure is presented for point location in convex planar subdivisions when the distribution of queries is known in advance. The data structure has an expected query time that differs from the optimal one by only lower order terms in the linear comparison tree model.

AB - A data structure is presented for point location in convex planar subdivisions when the distribution of queries is known in advance. The data structure has an expected query time that differs from the optimal one by only lower order terms in the linear comparison tree model.

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

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

M3 - Conference contribution

AN - SCOPUS:58449129127

SN - 9780898716474

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

SP - 912

EP - 921

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

T2 - 19th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 20 January 2008 through 22 January 2008

ER -

Distribution-sensitive point location in convex subdivisions

Abstract

Publication series

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this