Expected asymptotically optimal planar point location

被引：21

作者：

Iacono, J ^{[1
]}

机构：

[1] Polytech Univ, Dept Comp & Informat Sci, Brooklyn, NY 11201 USA

来源：

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 2004年 / 29卷 / 01期

基金：

美国国家科学基金会;

关键词：

point location; distribution-sensitive data structures;

D O I：

10.1016/j.comgeo.2004.03.010

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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. (C) 2004 Elsevier B.V. All rights reserved.

引用

页码：19 / 22

页数：4

共 10 条

[1]

Arya S, 2001, SIAM PROC S, P262

[2]

Arya S, 2001, SIAM PROC S, P256

[3]

Arya S, 2000, LECT NOTES COMPUT SC, V1851, P353

[4]

ARYA S, 2000, FDN COMPUTER SCI, P208

[5]

GHAZELLE B, 1991, DISCRETE COMPUT GEOM, V6, P485

[6]

Goodrich M.T, 1997, S DISCRETE ALGORITHM, P767

[7]

Iacono J, 2001, SIAM PROC S, P340

[8] OPTIMAL SEARCH IN PLANAR SUBDIVISIONS [J].

KIRKPATRICK, D .

SIAM JOURNAL ON COMPUTING, 1983, 12 (01) :28-35

[9]

MULMULEY K, 1977, SIAM J COMPUT, V6, P235

[10]

Seidel R., 1991, Computational Geometry: Theory and Applications, V1, P51, DOI 10.1016/0925-7721(91)90012-4

← 1 →