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 条
  • [41] On convex hull of Gaussian samples
    Youri Davydov
    Lithuanian Mathematical Journal, 2011, 51 : 171 - 179
  • [42] On Privacy Preserving Convex Hull
    Hans, Sandeep
    Addepalli, Sarat C.
    Gupta, Anuj
    Srinathan, Kannan
    2009 INTERNATIONAL CONFERENCE ON AVAILABILITY, RELIABILITY, AND SECURITY (ARES), VOLS 1 AND 2, 2009, : 187 - 192
  • [43] On efficiency in convex hull of DMUs
    Soltanifar, Mehdi
    Jahanshahloo, Gholam Reza
    Lotfi, Farhad Hosseinzadeh
    Mansourzadeh, Seyyed Mehdi
    APPLIED MATHEMATICAL MODELLING, 2013, 37 (04) : 2267 - 2278
  • [44] Convex hull properties and algorithms
    Zhang, Xianquan
    Tang, Zhenjun
    Yu, Jinhui
    Guo, Mingming
    Jiang, Lianyuan
    APPLIED MATHEMATICS AND COMPUTATION, 2010, 216 (11) : 3209 - 3218
  • [45] On the convex hull of projective planes
    Maurras, Jean-Francois
    Nedev, Roumen
    RAIRO-OPERATIONS RESEARCH, 2008, 42 (03) : 285 - 289
  • [46] The Convex Hull of Freeform Surfaces
    J.-K. Seong
    G. Elber
    J. K. Johnstone
    M.-S. Kim
    Computing, 2004, 72 : 171 - 183
  • [47] The Randomized Integer Convex Hull
    Imre Bárány
    Jirí Matousek
    Discrete & Computational Geometry, 2005, 33 : 3 - 25
  • [48] On the computation of the digital convex hull and circular hull of a digital region
    Chaudhuri, BB
    Rosenfeld, A
    PATTERN RECOGNITION, 1998, 31 (12) : 2007 - 2016
  • [49] A FAST AND COMPLETE CONVEX-HULL ALGORITHM ARCHITECTURE BASED ON ELLIPSE AND ELASTIC ELLIPSE METHODS
    Wu, Xue Gang
    Fang, Bin
    Tang, Yuan Yan
    Wang, Patrick Shen-Pei
    INTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE, 2013, 27 (08)
  • [50] 3D fast convex-hull-based evolutionary multiobjective optimization algorithm
    Zhao, Jiaqi
    Jiao, Licheng
    Liu, Fang
    Fernandes, Vitor Basto
    Yevseyeva, Iryna
    Xia, Shixiong
    Emmerich, Michael T. M.
    APPLIED SOFT COMPUTING, 2018, 67 : 322 - 336
12345