A CONVEX HULL ALGORITHM FOR POINTS WITH APPROXIMATELY KNOWN POSITIONS

被引：5

作者：

Franciosa, Paolo Giulio ^{[1
]}

Gaibisso, Carlo ^{[2
]}

Gambosi, Giorgio ^{[3
]}

Talamo, Maurizio ^{[1
]}

机构：

[1] Univ Rome La Sapienza, Dipartimento Infomat & Sistemist, I-00198 Rome, Italy

[2] CNR, Ist Anal Sistemi & Informat, I-00185 Rome, Italy

[3] Univ Aquila, Dipartimento Matemat Pura & Applicata, I-67010 Laquila, Italy

来源：

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS | 1994年 / 4卷 / 02期

关键词：

Computational geometry; convex hull; incremental algorithms; approximated algorithms; scaling; spatial data;

D O I：

10.1142/S0218195994000100

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We consider the problem of deriving good approximations of the convex hull of a set of points in the plane in the realistic case that only arbitrary finite approximations of the real valued coordinates can be known. In particular, the algorithm we introduce derives sequences of improved certified approximations converging to the exact solution, at the same time allowing the insertion of new points to the problem instance. The complexity analysis of the algorithm is performed by referring to a suitable computation model, based on a RAM with logarithmic costs, and the derived space and time bounds are shown to be competitive with respect to current off-line algorithms.

引用

页码：153 / 163

页数：11

共 15 条

[1] ANOTHER EFFICIENT ALGORITHM FOR CONVEX HULLS IN 2 DIMENSIONS [J].

ANDREW, AM .

INFORMATION PROCESSING LETTERS, 1979, 9 (05) :216-219

[2] ON THE COMPLEXITY OF FINDING THE CONVEX-HULL OF A SET OF POINTS [J].

AVIS, D .

DISCRETE APPLIED MATHEMATICS, 1982, 4 (02) :81-86

[3] APPROXIMATION ALGORITHMS FOR CONVEX HULLS [J].

BENTLEY, JL ;

FAUST, MG ;

PREPARATA, FP .

COMMUNICATIONS OF THE ACM, 1982, 25 (01) :64-68

[4] CONVEX HULL OF A FINITE SET OF POINTS IN 2 DIMENSIONS [J].

BYKAT, A .

INFORMATION PROCESSING LETTERS, 1978, 7 (06) :296-298

[5] THEORETICAL IMPROVEMENTS IN ALGORITHMIC EFFICIENCY FOR NETWORK FLOW PROBLEMS [J].

EDMONDS, J ;

KARP, RM .

JOURNAL OF THE ACM, 1972, 19 (02) :248-&

[6]

Franciosa P. G., 1992, R301 I AN SIST INF

[7]

GABOW HN, 1985, J COMPUT SYST SCI, V31, P148, DOI 10.1016/0022-0000(85)90039-X

[8]

GABOW HN, 1984, P 16 ANN ACM S THEOR, P135

[9]

Goodrich M. T., 1993, Computational Geometry: Theory and Applications, V2, P267, DOI 10.1016/0925-7721(93)90023-Y

[10]

Graham R. L., 1972, Information Processing Letters, V1, P132, DOI 10.1016/0020-0190(72)90045-2

← 1 2 →