Data structures for mobile data

被引：129

作者：

Basch, J ^{[1
]}

Guibas, LJ

Hershberger, J

机构：

[1] Stanford Univ, Dept Comp Sci, Stanford, CA 94305 USA

[2] Mentor Graph Corp, Wilsonville, OR 97070 USA

来源：

JOURNAL OF ALGORITHMS | 1999年 / 31卷 / 01期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1006/jagm.1998.0988

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A kinetic data structure (KDS) maintains an attribute of interest in a system of geometric objects undergoing continuous motion. In this paper we develop a concentual framework for kinetic data structures, we propose a number of criteria for the quality of such structures, and we describe a number of fundamental techniques for their design. We illustrate these general concepts by presenting kinetic data structures for maintaining the convex hull and the closest pair of moving points in the plane; these structures behave well according to the proposed quality criteria for KDSs. (C) 1999 Academic Press.

引用

页码：1 / 28

页数：28

共 28 条

[11]

BENTLEY JL, 1979, IEEE T COMPUT, V28, P643, DOI 10.1109/TC.1979.1675432

[12]

Bespamyatnikh S. N., 1995, Proceedings of the Eleventh Annual Symposium on Computational Geometry, P152, DOI 10.1145/220279.220296

[13] ALGORITHMS FOR REPORTING AND COUNTING GEOMETRIC INTERSECTIONS - COMMENTS [J].

BROWN, KQ .

IEEE TRANSACTIONS ON COMPUTERS, 1981, 30 (02) :147-148

[14]

CALLAHAN PB, 1995, PROCEEDINGS OF THE SIXTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P263

[15] CONSTRUCTING BELTS IN TWO-DIMENSIONAL ARRANGEMENTS WITH APPLICATIONS [J].

EDELSBRUNNER, H ;

WELZL, E .

SIAM JOURNAL ON COMPUTING, 1986, 15 (01) :271-284

[16] VORONOI DIAGRAMS OF MOVING POINTS IN THE PLANE [J].

Fu, Jyh-Jong ;

Lee, R. C. T. .

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1991, 1 (01) :23-32

[17]

GOLIN M, 1993, PROCEEDINGS OF THE FOURTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P301

[18] FINDING THE UPPER ENVELOPE OF N LINE SEGMENTS IN O(N LOG N) TIME [J].

HERSHBERGER, J .

INFORMATION PROCESSING LETTERS, 1989, 33 (04) :169-174

[19] APPLICATIONS OF A SEMIDYNAMIC CONVEX-HULL ALGORITHM [J].

HERSHBERGER, J ;

SURI, S .

BIT, 1992, 32 (02) :249-267

[20]

Kapoor S., 1994, Proceedings of the Tenth Annual Symposium on Computational Geometry, P165, DOI 10.1145/177424.177621

← 1 2 3 →