[comp.theory] Convex Hull Algorithm Wanted

maes@prl.philips.nl (Maurice Maes) (01/02/91)

We need a (preferably FORTRAN77) algorithm to determine the convex
hull of a given set of points in the Euclidean plane.
Does anybody have such an algorithm, or does anybody know
where to obtain algorithms for standard Computational Geometry problems?

Please mail or post, thanks



Maurice Maes

xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) (01/03/91)

In article <2432@prles2.prl.philips.nl> maes@prl.philips.nl (Maurice Maes) writes:
>We need a (preferably FORTRAN77) algorithm to determine the convex
>hull of a given set of points in the Euclidean plane.
>Does anybody have such an algorithm, or does anybody know
>where to obtain algorithms for standard Computational Geometry problems?

Well, your standard sourcebook is Preparata and Shamos' Computational Geometry.

You don't want to accept someone elses code for this particular function,
in any case, since there have been some recent advances improving the
order of the algorithm.  A literature search is in order.  Start with ACM's
Transactions on Graphics, on a guess.

Kent, the man from xanth.
<xanthian@Zorch.SF-Bay.ORG> <xanthian@well.sf.ca.us>

steveb@orca.wv.tek.com (01/03/91)

You might look at section VIII.2 (pg 93) of:

	Mehlhorn, Kurt "Multi-dimensional Searching and
	Computational Geometry"  EATCS monographs on
	Theoretical Computer Science, Springer-Verlag 1984.

There is no code but the theoretical discussion is very good 
and the algorithms are relatively well described.


Steve