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

```

• Prev by Date: webMathematica-based on-line learning system?
• Next by Date: Re: DifferenceOrder command
• Previous by thread: Re: Re: Much faster ConvexHull implementation
• Next by thread: Re: Much faster ConvexHull implementation