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 条
  • [1] DEEPHULL: FAST CONVEX HULL APPROXIMATION IN HIGH DIMENSIONS
    Balestriero, Randall
    Wang, Zichao
    Baraniuk, Richard G.
    2022 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING (ICASSP), 2022, : 3888 - 3892
  • [2] Fast Convex Hull by a Geometric Approach
    Beltran-Herrera, Alberto
    Mendoza, Sonia
    PATTERN RECOGNITION, 2018, 10880 : 51 - 61
  • [3] Inner δ-approximation of the convex hull of finite sets
    Hoang, Nam-Dung
    Linh, Nguyen Kieu
    Phu, Hoang Xuan
    COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2025,
  • [4] A Fast Convex Hull Algorithm for Binary Image
    Zhang, Xianquan
    Tang, Zhenjun
    Yu, Jinhui
    Guo, Mingming
    INFORMATICA-JOURNAL OF COMPUTING AND INFORMATICS, 2010, 34 (03): : 369 - 376
  • [5] A Preprocessing Technique for Fast Convex Hull Computation
    Alshamrani, Reham
    Alshehri, Fatimah
    Kurdi, Heba
    11TH INTERNATIONAL CONFERENCE ON AMBIENT SYSTEMS, NETWORKS AND TECHNOLOGIES (ANT) / THE 3RD INTERNATIONAL CONFERENCE ON EMERGING DATA AND INDUSTRY 4.0 (EDI40) / AFFILIATED WORKSHOPS, 2020, 170 : 317 - 324
  • [6] A Fast Convex Hull Algorithm of Planar Point Set
    Jiang, Hong-fei
    MECHATRONICS AND INTELLIGENT MATERIALS III, PTS 1-3, 2013, 706-708 : 1852 - 1855
  • [7] Fast inline convex hull algorithm in any dimension
    Delpias, C
    6TH WORLD MULTICONFERENCE ON SYSTEMICS, CYBERNETICS AND INFORMATICS, VOL XI, PROCEEDINGS: COMPUTER SCIENCE II, 2002, : 171 - 175
  • [8] Fast convex hull classifier based on random projection
    Gu X.-Q.
    Zhang C.
    Ni T.-G.
    Kongzhi yu Juece/Control and Decision, 2020, 35 (05): : 1151 - 1158
  • [9] Fast Encoding Parameter Selection For Convex Hull Video Encoding
    Wu, Ping-Hao
    Kondratenko, Volodymyr
    Katsavounidis, Ioannis
    APPLICATIONS OF DIGITAL IMAGE PROCESSING XLIII, 2020, 11510
  • [10] A fast convex hull algorithm inspired by human visual perception
    Liu, Runzong
    Tang, Yuan Yan
    Chan, Patrick P. K.
    MULTIMEDIA TOOLS AND APPLICATIONS, 2018, 77 (23) : 31221 - 31237
12345