From: Dana Swift <swift@ocean.washington.edu>
Newsgroups: sci.math.num-analysis
Subject: Re: Evaluating the convex hull of a number of points
Date: Thu, 24 Oct 1996 17:46:25 -0700

On 24 Oct 1996, Michael C. Herron wrote:

> 
> In order to evaluate a function f(x), I have to determine if x is in
> the convex hull of a bunch of points (in R^2).  Some code I am writing
> must evaluate f thousands of times.
> 
> Can someone refer me to efficient methods that people have developed
> to do this?  I can code up inefficient algorithms to determine if a
> given x is in the convex hull of the points, but I am curious as to
> existing algorithms.

The most efficient method known for constructing the convex hull of an 
arbitrary set of points in 2-D is referred to as the Graham Scan.  It's 
really pretty straightforward to code.  The inefficient method you are 
might be referring to is often called a "shrink-wrap" and requires a 
number of comparisons that is proportional to the square of the number 
(n) of points.  The Graham Scan is an order n*log2(n) which is 
considerably more efficient than n^2.  I'd refer you to Sedgewick's 
book "Algorithms in C" (now also available for C++) for a reasonably good 
description.  Detecting if a point is inside a convex hull is not too 
hard either and is also discussed in Sedgewick's book.

-dds

=========================================================================
= Dana D. Swift                              Office: (206) 543-6697     =
= School of Oceanography      o__    ____    Fax:    (206) 685-3354     =
= University of Washington   _,>/'_  -----   swift@ocean.washington.edu =
= Box 357940                (_) \(_) ------  ORB 106                    =
= Seattle, WA  98195                                                    =
= http://www.ocean.washington.edu/people/staff/swift/Swift.html         =
=========================================================================
==============================================================================

Newsgroups: sci.math.num-analysis
From: clarkson@research.att.com (Ken Clarkson)
Subject: Re: Evaluating the convex hull of a number of points
Date: Tue, 29 Oct 1996 14:35:44 GMT

In article <54omos$6b2@gsb-birr.Stanford.EDU>, pherron@gsb-birr.Stanford.EDU (Michael C. Herron) writes:
|> Can someone refer me to efficient methods that people have developed
|> to do this?  I can code up inefficient algorithms to determine if a
|> given x is in the convex hull of the points, but I am curious as to
|> existing algorithms.

At
http://www.geom.umn.edu:80/software/cglist/ there is a collection
of links to code for geometric problems, and at
http://www.geom.umn.edu:80/software/cglist/lowdvod.html,
there are pointers to various low-dimensional geometric algorithms,
including a few 2-dimensional convex hull codes.  I wrote one of
these, in C; it's at
http://cm.bell-labs.com/who/clarkson/2dch.c.
My code is somewhat like Graham scan, but uses two sorts by x-coordinate
instead of one sort by angle, and explicitly computes the
"upper hull" and the "lower hull" of the points.

I take it that you want to compute the hull, and then check for
various points p if they are in the hull.  You could do this
with my code by checking if p is above the upper hull or below the
lower hull.  To check if p is above the upper hull, you'd
find the two consecutive hull vertices whose x coordinates
bracket the x-coordinate of p, and then check if p is above
the line segment between them.  This could be done using
the primitives already in my code.  The dominant cost here is
probably finding those two consecutive points, which could be done
by binary search in O(log n) time for n vertices, or by bucketing
in expected constant time for reasonable point sets.  In any
case, the test should take fewer than maybe 20 lines of code.

-Ken