Services & Resources / Wolfram Forums
MathGroup Archive
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2005

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Much faster ConvexHull implementation

  • To: mathgroup at
  • Subject: [mg55715] Re: Much faster ConvexHull implementation
  • From: nafod40 <noneya at>
  • Date: Mon, 4 Apr 2005 00:59:20 -0400 (EDT)
  • Organization: Penn State University, Center for Academic Computing
  • References: <d1tvc0$rli$> <> <> <011401c53310$74dde680$6400a8c0@Main> <> <02a501c533ac$f76aa4c0$6400a8c0@Main> <> <d2b547$79l$> <d2j9ld$s2$> <d2le52$ai8$>
  • Sender: owner-wri-mathgroup at

Carl K. Woll wrote:

> However, in case you are still interested, I've improved convex[] on my 
> machine so that it's about an order of magnitude faster for random points in 
> the unit square and 2 to 3 times faster for finding the convex hull of the 
> vertices of a convex polygon. In fact, it seems that the scaling is not much 
> worse than linear for my test cases with up to a million points. I suppose 
> this may be because at least part of the O(n log n) dependence is due to 
> sorting, and since Sort (as well as Ordering) is an extremely quick built-in 
> function, it takes extremely large data sets before Sort dominates the 
> scaling. I'm sure there are also pathological cases where the scaling would 
> be much worse, but I haven't spent the time to construct any. I could send a 
> notebook with this newer algorithm to you if you are interested in testing 
> it.

I did work on algorithms to identify the pareto frontier, which is a 
similar problem to finding the convex hull. Here were two papers that 
addressed it. This was Jon Bentley's PhD thesis topic a few (or more) 
years ago. The second talks about dealing with randomized data sets, 
which result in not all that many points on the convex hull compared to 
the total number of points in the set.

1Bentley, J., "Multidimensional Divide-and-Conquer," Communications of 
the ACM, Vol. 23, No. 4, 1980, pp. 214-229.

1Bentley, J., Clarkson, K. and Levine, D., "Fast linear expected-time 
algorithms for computing maxima and convex hulls," Annual ACM-SIAM 
Symposium on Discrete Algorithm, 1990, pp. 509-517.Fast linear 
expected-time algorithms for computing maxima and convex hulls

  • Prev by Date: Re: Re: power series in more than one variables
  • Next by Date: Numerical accuracy of Hypergeometric2F1
  • Previous by thread: Re: Much faster ConvexHull implementation
  • Next by thread: Re: Much faster ConvexHull implementation