From: Jeff Erickson <jeffe@sal.cs.uiuc.edu>
Newsgroups: sci.math.research
Subject: Re: Smallest circle enclosing a set of points
Date: Thu, 27 Aug 1998 16:42:54 -0500

Fred S Long wrote:
> 
> Jeff Erickson wrote:
> > tchow[address deleted] wrote:
> > > ...find the center and radius of a smallest
> > > circle enclosing all the points.
> >
> > It can be found in linear time using an algorithm of Welzl.
>
> Does this imply that a convex hull can be built in linear time?

No.  The smallest enclosing circle doesn't give you very much
information about the convex hull!

> If I recall, a convex hull using a Graham Scan was O(n log n)
> because of a sort.

Yes.  Sorting and 2d convex hulls are equally hard.  We can compute
convex hulls in O(n) time after sorting the points from left to right,
and we can sort a set of numbers in O(n) time after replacing each
number x with the point (x,x^2) and computing the convex hull.

-- 
Jeff Erickson                                        jeffe@cs.uiuc.edu
Computer Science Department           http://www.uiuc.edu/ph/www/jeffe
University of Illinois, Urbana-Champaign