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 条
  • [31] Asymptotics of the convex hull of spherically symmetric samples
    Hashorva, Enkelejd
    DISCRETE APPLIED MATHEMATICS, 2011, 159 (04) : 201 - 211
  • [32] On the boundary structure of the convex hull of random points
    Buchta, Christian
    ADVANCES IN GEOMETRY, 2012, 12 (01) : 179 - 190
  • [33] On the volume of the convex hull of two convex bodies
    Horvath, Akos G.
    Langi, Zsolt
    MONATSHEFTE FUR MATHEMATIK, 2014, 174 (02): : 219 - 229
  • [34] THE CONVEX-HULL OF A SET OF CONVEX POLYGONS
    CHEN, H
    ROKNE, J
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1992, 42 (3-4) : 163 - 172
  • [35] On the volume of the convex hull of two convex bodies
    Ákos G. Horváth
    Zsolt Lángi
    Monatshefte für Mathematik, 2014, 174 : 219 - 229
  • [36] A fast algorithm to sample the number of vertexes and the area of the random convex hull on the unit square
    Ng, Chi Tim
    Lim, Johan
    Lee, Kyeong Eun
    Yu, Donghyeon
    Choi, Sujung
    COMPUTATIONAL STATISTICS, 2014, 29 (05) : 1187 - 1205
  • [37] A fast algorithm to sample the number of vertexes and the area of the random convex hull on the unit square
    Chi Tim Ng
    Johan Lim
    Kyeong Eun Lee
    Donghyeon Yu
    Sujung Choi
    Computational Statistics, 2014, 29 : 1187 - 1205
  • [38] A Variational Convex Hull Algorithm
    Li, Lingfeng
    Luo, Shousheng
    Tai, Xue-Cheng
    Yang, Jiang
    SCALE SPACE AND VARIATIONAL METHODS IN COMPUTER VISION, SSVM 2019, 2019, 11603 : 224 - 235
  • [39] ON CONVEX HULL OF GAUSSIAN SAMPLES
    Davydov, Youri
    LITHUANIAN MATHEMATICAL JOURNAL, 2011, 51 (02) : 171 - 179
  • [40] The convex hull of freeform surfaces
    Seong, JK
    Elber, G
    Johnstone, JK
    Kim, MS
    COMPUTING, 2004, 72 (1-2) : 171 - 183
12345