Fast approximation of convex hull

被引：0

作者：

Kavan, Ladislav ^{[1
]}

Kolingerova, Ivana ^{[2
]}

Zara, Jiri ^{[1
]}

机构：

[1] FEE CTU Prague, Karlovo Nam 13, Prague 2, Czech Republic

[2] Univ West Bohemia, Plzen, Czech Republic

来源：

PROCEEDINGS OF THE IASTED INTERNATIONAL CONFERENCE ON ADVANCES IN COMPUTER SCIENCE AND TECHNOLOGY | 2006年

关键词：

convex hull; approximation; linear time;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

The construction of a planar convex hull is an essential operation in computational geometry. It has been proven that the time complexity of an exact solution is Omega(NlogN). In this paper, we describe an algorithm with time complexity O(N + k(2)), where k is parameter controlling the approximation quality. This is beneficial for applications processing a large number of points without necessity of an exact solution. A formula for upper bound of the approximation error is presented.

引用

页码：101 / +

页数：2

共 50 条

[21] A fast parallel algorithm for finding the convex hull of a sorted point set
Berkman, O
Schieber, B
Vishkin, U
INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1996, 6 (02) : 231 - 241
[22] FAST COMPONENT LABELING AND CONVEX-HULL COMPUTATION ON RECONFIGURABLE MESHES
OLARIU, S
SCHWING, JL
ZHANG, JY
IMAGE AND VISION COMPUTING, 1993, 11 (07) : 447 - 455
[23] Extended convex hull
Fukuda, K
Liebling, TM
Lütolf, C
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2001, 20 (1-2): : 13 - 23
[24] On FastMap and the convex hull of multivariate data: Toward fast and robust dimension reduction
Ostrouchov, G
Samatova, NF
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2005, 27 (08) : 1340 - 1343
[25] A FAST ALGORITHM FOR CONVEX-HULL EXTRACTION IN 2D IMAGES
YE, QZ
PATTERN RECOGNITION LETTERS, 1995, 16 (05) : 531 - 537
[26] CONVEX_HULL - A Pascal program for determining the convex hull for planar sets
Yamamoto, JK
COMPUTERS & GEOSCIENCES, 1997, 23 (07) : 725 - 738
[27] Fast data reduction by space partitioning via convex hull and MBR computation
Giorginis, Thomas
Ougiaroglou, Stefanos
Evangelidis, Georgios
Dervos, Dimitris A.
PATTERN RECOGNITION, 2022, 126
[28] A COUNTER－EXAMPLE TO A FAST ALGORITHM FOR FINDING THE CONVEX HULL OF A SIMPLE POLYGON
Godfried Toussaint
Computer Aided Drafting,Design and Manufacturing, 1994, Design and Manufacturing.1994 (02) : 1 - 4
[29] Area and Perimeter of the Convex Hull of Stochastic Points
Perez-Lantero, Pablo
COMPUTER JOURNAL, 2016, 59 (08) : 1144 - 1154
[30] Convolution and subordination in the convex hull of convex mappings
Sokól, J
APPLIED MATHEMATICS LETTERS, 2006, 19 (04) : 303 - 306

← 1 2 3 4 5 →