CODEWITHSUNDEEP
computational-geometrysortingconvex-hull
Alexey Maksimov
Alexey Maksimov

Reputation: 11

Convex hull algorithms for sorted set of points

I need an algorithm for computation convex hulls for sorted set of points in 3 and higher dimensions. Also I need in lower part of a convex hull and it is not necessary to construct a whole convex hull. Are there any efficient and quick algorithms for my purposes?

Upvotes: 1

Views: 1178

Answers (3)

David
David

Reputation: 51

GPL C++ code for finding the convex hull of points in R3 is available at http://www.newtonapples.net/code/NewtonAppleWrapper_11Feb2016.tar.gz The algorithm is based on sorting the points in z(x(y)) then sequentially wrapping points into a hull. Rather appealingly the algorithm has been named after a chocolate.

Upvotes: 0

kiriloff
kiriloff

Reputation: 26333

I implemented this hull algorithm for convex hull finding, posted on GitHub. This is Python and can give you results as:

enter image description here

Upvotes: 1

Joseph O'Rourke
Joseph O'Rourke

Reputation: 4406

I believe it was established by Seidel that having the points sorted does not help in terms of asymptotic time complexity, and certainly the lower half can be almost the entire hull, so that will not help either. The randomized incremental (Clarkson and Shor) is perhaps the best choice. Here is an applet illustration of that algorithm: Tufts link.

Upvotes: 1

Related Questions