research-article

A Total Order Heuristic-Based Convex Hull Algorithm for Points in the Plane

Author:

Abel J.P. GomesAuthors Info & Claims

Computer-Aided Design, Volume 70, Issue C

Pages 153 - 160

https://doi.org/10.1016/j.cad.2015.07.013

Published: 01 January 2016 Publication History

Abstract

Computing the convex hull of a set of points is a fundamental operation in many research fields, including geometric computing, computer graphics, computer vision, robotics, and so forth. This problem is particularly challenging when the number of points goes beyond some millions. In this article, we describe a very fast algorithm that copes with millions of points in a short period of time without using any kind of parallel computing. This has been made possible because the algorithm reduces to a sorting problem of the input point set, what dramatically minimizes the geometric computations (e.g., angles, distances, and so forth) that are typical in other algorithms. When compared with popular convex hull algorithms (namely, Graham's scan, Andrew's monotone chain, Jarvis' gift wrapping, Chan's, and Quickhull), our algorithm is capable of generating the convex hull of a point set in the plane much faster than those five algorithms without penalties in memory space. We propose a 2D convex hull algorithm based on comparison operators.We propose a 2D convex hull algorithm that outperforms Quickhull.We propose a 2D non-convex hull algorithm.

References

[1]

F.P. Preparata, S.J. Hong, Convex hulls of finite sets of points in two and three dimensions, Commun ACM, 20 (1977) 87-93.

Digital Library

[2]

S. Srungarapu, D. Reddy, K. Kothapalli, P. Narayanan, Fast two dimensional convex hull on the GPU, in: Proceedings of the 25th IEEE international conference on advanced information networking and applications, IEEE Press, 2011, pp. 7-12.

[3]

B. Goldluecke, D. Cremers, Convex relaxation for multilabel problems with product label spaces, in: Lecture notes in computer science, vol. 6315, Springer, Berlin (Heidelberg), 2010, pp. 225-238.

[4]

G. Toussaint, R. Foulsen, Some new algorithms and software implementation methods for pattern recognition research, in: Proceedings of the 3rd IEEE international computer software and applications conference, IEEE Press, 1979, pp. 55-58.

[5]

S. Liu-Yu, M. Thonnat, Description of object shapes by apparent boundary and convex hull, Pattern Recognit, 26 (1993) 95-107.

[6]

H. Hahn, Y. Han, Recognition of 3D object using attributed relation graph of silhouette's extended convex hull, in: Lecture notes in computer science, vol. 4292, Springer-Verlag, 2006, pp. 126-135.

[7]

H.D. Sherali, J. Smith, S.Z. Selim, Convex hull representations of models for computing collisions between multiple bodies, European J Oper Res, 135 (2001) 514-526.

[8]

K. Okada, M. Inaba, H. Inoue, Walking navigation system of humanoid robot using stereo vision based floor recognition and path planning with multi-layered body image, in: Proceedings of the 2003 IEEE/RSJ international conference on intelligent robots and systems, Vol. 3, IEEE Press, 2003, pp. 2155-2160.

[9]

M. Strandberg, Robot path planning: An object-oriented approach, Automatic Control, Department of Signals, Sensors and Systems, Royal Institute of Technology (KTH), Stockholm (Sweden), 2004.

[10]

O. Fuentes, Automatic determination of stellar atmospheric parameters using neural networks and instance-based machine learning, Exp Astron, 12 (2001) 21-31.

[11]

N.R. Amundson, A. Caboussat, J. He, J.H. Seinfeld, An optimization problem related to the modeling of atmospheric organic aerosols, C R Math, 340 (2005) 765-768.

[12]

Y. Wang, L.-Y. Wu, J.-H. Zhang, Z.-W. Zhan, X.-S. Zhang, L. Chen, Evaluating protein similarity from coarse structures, IEEE/ACM Trans Comput Biol Bioinf, 6 (2009) 583-593.

Digital Library

[13]

D. Avis, D. Bremner, R. Seidel, How good are convex hull algorithms?, Comput Geom, 7 (1997) 265-301.

Digital Library

[14]

R.L. Graham, An efficient algorithm for determining the convex hull of a finite planar set, Inform Process Lett, 1 (1972) 132-133.

[15]

R.A. Jarvis, On the identification of the convex hull of a finite set of points in the plane, Inform Process Lett, 2 (1973) 18-21.

[16]

A.M. Andrew, Another efficient algorithm for convex hulls in two dimensions, Inform Process Lett, 9 (1979) 216-219.

[17]

C.B. Barber, D.P. Dobkin, H. Huhdanpaa, The quickhull algorithm for convex hulls, ACM Trans Math Softw, 22 (1996) 469-483.

Digital Library

[18]

M. Kallay, The complexity of incremental convex hull algorithms in R d, Inform Process Lett, 19 (1984) 197.

[19]

D. Musser, Introspective sorting and selection algorithms, Softw - Pract Exp, 27 (1997) 983-993.

Digital Library

[20]

R. Gonzalez, R. Woods, Digital image processing, Prentice Hall, Inc., New Jersey (USA), 2008.

[21]

T. Chan, Output-sensitive results on convex hulls, extreme points, and related problems, Discrete Comput Geom, 16 (1996) 369-387.

Digital Library

Cited By

Fabrizio J(2023)How to compute the convex hull of a binary shape? A real-time algorithm to compute the convex hull of a binary shapeJournal of Real-Time Image Processing10.1007/s11554-023-01359-820:6Online publication date: 13-Sep-2023
https://dl.acm.org/doi/10.1007/s11554-023-01359-8
Xiao ZGao JWu DZhang LChen X(2020)A fast 3D object recognition algorithm using plane-constrained point pair featuresMultimedia Tools and Applications10.1007/s11042-020-09525-x79:39-40(29305-29325)Online publication date: 11-Aug-2020
https://dl.acm.org/doi/10.1007/s11042-020-09525-x

A Total Order Heuristic-Based Convex Hull Algorithm for Points in the Plane
1. Computing methodologies
  1. Computer graphics
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Convex hulls of spheres and convex hulls of disjoint convex polytopes

Given a set @S of spheres in E^d, with d>=3 and d odd, having a constant number of m distinct radii @r"1,@r"2,...,@r"m, we show that the worst-case combinatorial complexity of the convex hull of @S is @Q(@__ __"1"=<"i"<>"j"=<"mn"in"j^@__ __^d^2^@__ __), ...
Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes
SoCG '11: Proceedings of the twenty-seventh annual symposium on Computational geometry

Given a set Σ of spheres in E^d, with d≥3 and d odd, having a fixed number of m distinct radii ρ₁,ρ₂,...,ρ_m, we show that the worst-case combinatorial complexity of the convex hull CH_d(Σ) of Σ is Θ(Σ_{{1≤i≠j≤m}}n_in_j^{⌊ d/2 ⌋}), where n_i is the number of ...
-Concave hull, a generalization of convex hull

Bounding hulls such as convex hull, -shape, -hull, concave hull, crust, etc. offer a wide variety of useful applications. In this paper, we explore another bounding hull, namely -concave hull, as a generalization of convex hull. The parameter determines ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computer-Aided Design

Computer-Aided Design Volume 70, Issue C

January 2016

204 pages

ISSN:0010-4485

Issue’s Table of Contents

Copyright © Elsevier Ltd.

Publisher

Butterworth-Heinemann

United States

Publication History

Published: 01 January 2016

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fabrizio J(2023)How to compute the convex hull of a binary shape? A real-time algorithm to compute the convex hull of a binary shapeJournal of Real-Time Image Processing10.1007/s11554-023-01359-820:6Online publication date: 13-Sep-2023
https://dl.acm.org/doi/10.1007/s11554-023-01359-8
Xiao ZGao JWu DZhang LChen X(2020)A fast 3D object recognition algorithm using plane-constrained point pair featuresMultimedia Tools and Applications10.1007/s11042-020-09525-x79:39-40(29305-29325)Online publication date: 11-Aug-2020
https://dl.acm.org/doi/10.1007/s11042-020-09525-x

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents