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

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