Semi-online maintenance of geometric optima and measures

被引：34

作者：

Chan, TM ^{[1
]}

机构：

[1] Univ Waterloo, Sch Comp Sci, Waterloo, ON N2L 3G1, Canada

来源：

SIAM JOURNAL ON COMPUTING | 2003年 / 32卷 / 03期

关键词：

computational geometry; dynamic data structures;

D O I：

10.1137/S0097539702404389

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We give the first nontrivial worst-case results for dynamic versions of various basic geometric optimization and measure problems under the semi-online model, where during the insertion of an object we are told when the object is to be deleted. Problems that we can solve with sublinear update time include the Hausdorff distance of two point sets, discrete 1-center, largest empty circle, convex hull volume in three dimensions, volume of the union of axis-parallel cubes, and minimum enclosing rectangle. The decision versions of the Hausdorff distance and discrete 1-center problems can be solved fully dynamically. Some applications are mentioned.

引用

页码：700 / 716

页数：17

共 28 条

[1]

Agarwal P.K., 1999, ADV DISCRETE COMPUTA, V223, P1, DOI [10.1090/conm/223/03131, DOI 10.1090/conm/223/03131]

[2] DYNAMIC HALF-SPACE RANGE REPORTING AND ITS APPLICATIONS [J].

AGARWAL, PK ;

MATOUSEK, J .

ALGORITHMICA, 1995, 13 (04) :325-345

[3] The discrete 2-center problem [J].

Agarwal, PK ;

Sharir, M ;

Welzl, E .

DISCRETE & COMPUTATIONAL GEOMETRY, 1998, 20 (03) :287-305

[4] ON RANGE SEARCHING WITH SEMIALGEBRAIC SETS [J].

AGARWAL, PK ;

MATOUSEK, J .

DISCRETE & COMPUTATIONAL GEOMETRY, 1994, 11 (04) :393-418

[5]

[Anonymous], J ALGORITHMS

[6] Voronoi diagrams in higher dimensions under certain polyhedral distance functions [J].

Boissonnat, JD ;

Sharir, M ;

Tagansky, B ;

Yvinec, M .

DISCRETE & COMPUTATIONAL GEOMETRY, 1998, 19 (04) :485-519

[7] ALMOST OPTIMAL SET COVERS IN FINITE VC-DIMENSION [J].

BRONNIMANN, H ;

GOODRICH, MT .

DISCRETE & COMPUTATIONAL GEOMETRY, 1995, 14 (04) :463-479

[8]

CHAN TM, IN PRESS DISCRETE CO

[9] Geometric pattern matching in d-dimensional space [J].

Chew, LP ;

Dor, D ;

Efrat, A ;

Kedem, K .

DISCRETE & COMPUTATIONAL GEOMETRY, 1999, 21 (02) :257-274

[10] DYNAMIC ALGORITHMS IN COMPUTATIONAL GEOMETRY [J].

CHIANG, YJ ;

TAMASSIA, R .

PROCEEDINGS OF THE IEEE, 1992, 80 (09) :1412-1434

← 1 2 3 →