Re: Much faster ConvexHull implementation
- To: mathgroup at smc.vnet.net
- Subject: [mg55715] Re: Much faster ConvexHull implementation
- From: nafod40 <noneya at business.com>
- Date: Mon, 4 Apr 2005 00:59:20 -0400 (EDT)
- Organization: Penn State University, Center for Academic Computing
- References: <d1tvc0$rli$1@smc.vnet.net> <200503270742.CAA06233@smc.vnet.net> <opsoa9q5xpiz9bcq@monster.ma.dl.cox.net> <011401c53310$74dde680$6400a8c0@Main> <opsob4uhh3iz9bcq@monster.ma.dl.cox.net> <02a501c533ac$f76aa4c0$6400a8c0@Main> <opsoc793kbiz9bcq@monster.ma.dl.cox.net> <d2b547$79l$1@smc.vnet.net> <d2j9ld$s2$1@smc.vnet.net> <d2le52$ai8$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
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