Re: Much faster ConvexHull implementation

*To*: mathgroup at smc.vnet.net*Subject*: [mg55669] Re: Much faster ConvexHull implementation*From*: "Carl K. Woll" <carlw at u.washington.edu>*Date*: Sat, 2 Apr 2005 01:28:00 -0500 (EST)*Organization*: University of Washington*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>*Sender*: owner-wri-mathgroup at wolfram.com

"Ray Koopman" <koopman at sfu.ca> wrote in message news:d2j9ld$s2$1 at smc.vnet.net... > "Carl K. Woll" <carl at woll2woll.com> wrote in message > news:<d2b547$79l$1 at smc.vnet.net>... >> [...] [snip] > Here is the hull for 9 random points in the unit square: > > In[10]:= convex[pts = > {{0.358243,0.363412},{0.105996,0.669358},{0.672295,0.0448138}, > {0.0124393,0.672149},{0.728004,0.311669},{0.90424,0.545403}, > {0.99939,0.160133},{0.749434,0.963945},{0.355428,0.0788455}}] > > Out[10]= {7,6,8,4,4,9,3} > > Such duplication occurs fairly often for random points. > Is anyone else getting this? Have I copied something wrongly? > Ray, Let me first mention that I have an older version of Mathematica, where the built-in ConvexHull did seem to scale as O(n^2). However, I've been informed that newer versions of Mathematica should have a ConvexHull which does scale as O(n^2). So, getting my convex[] to work for you is probably not worth your trouble. I should also mention that my convex[] function is just the 2D Quickhull algorithm. 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. As far as your question on duplication, I don't have an answer. I took the code you posted, and ran it on my computer, and I did not get any duplicate points on your test input. I believe you may be getting duplicate points only at the left and/or right edges of your data set. At any rate, if you are interested in pursuing this further, please try out my newer convex[] first to see if the problem persists. Carl Woll