From: Jeff Erickson
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