An efficient convex hull algorithm for finite point sets in 3D based on the Method of Orienting Curves

Author： An Phan Thanh   Trang Le Hong  

Publisher： Taylor & Francis Ltd

ISSN： 0233-1934

Source： Optimization, Vol.62, Iss.7, 2013-07, pp. : 975-988

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

This article describes an efficient convex hull algorithm for finite point sets in 3D based on the idea of the Method of Orienting Curves (introduced by Phu in Optimization, 18 (1987) pp. 65-81, for solving optimal control problems with state constraints). The actual run times of our algorithm and known gift-wrapping algorithm on the set of random points (in uniform distribution) show that our algorithm runs significantly faster than the gift-wrapping one.

Related content

Method of orienting curves for determining the convex hull of a finite set of points in the plane

By Thanh An Phan  

Optimization, Vol. 59, Iss. 2, 2010-02 ,pp. : 175-179 (5)

Taylor & Francis Ltd

Access to resources Recommend Favorite

An interior-point method for minimizing convex functions on the convex hull of a point set

By Stoer Josef  

Optimization, Vol. 56, Iss. 4, 2007-08 ,pp. : 515-524 (10)

Taylor & Francis Ltd

Access to resources Recommend Favorite

Minimization of convex functions on the convex hull of a point set

By Botkin Nikolai  

Mathematical Methods of Operations Research, Vol. 62, Iss. 2, 2005-11 ,pp. : 167-185 (19)

Springer Publishing Company

Access to resources Recommend Favorite

Finite termination of the proximal point method for convex functions on Hadamard manifolds

By Bento G.C.   Neto J.X. Cruz  

Optimization, Vol. 63, Iss. 9, 2014-09 ,pp. : 1281-1288 (8)

Taylor & Francis Ltd

Access to resources Recommend Favorite

Covering the Convex Quadrilaterals of Point Sets

By Sakai Toshinori   Urrutia Jorge  

Graphs and Combinatorics, Vol. 23, Iss. 1, 2007-06 ,pp. : 343-357 (15)

Springer Publishing Company

Access to resources Recommend Favorite