Re: The minimum spanning circle problem
- To: mathgroup at smc.vnet.net
- Subject: [mg4514] Re: The minimum spanning circle problem
- From: David Eppstein <eppstein at wormwood.ICS.UCI.EDU>
- Date: Fri, 2 Aug 1996 02:22:40 -0400
- Organization: UC Irvine Department of ICS
- Sender: owner-wri-mathgroup at wolfram.com
Riccardo Rigon <rrigon at acs.tamu.edu> writes:
> given a set of n points {p_1, ....p_n} in the plane find the center
> and the radius of the smallest circle such that no point is exterior
> to the circle.
This can be solved in linear time. For a good easy-to-implement method,
see R. Seidel, Small-dimensional linear programming and convex hulls
made easy, 6th ACM Symp. Computational Geometry (1990) 211-215 and
Discrete & Computational Geometry 6 (1991) 423-434.
> Actually I am looking for the distance of the two
> farthest apart points of the set, and I know that
> my points are the vertices of a convex hull.
That is a completely different problem. It can be solved in linear time
once the convex hull is known; otherwise it requires O(n log n) time.
The solution is described in Preparata and Shamos, Computational Geometry:
an Introduction, Springer-Verlag 1985, pp. 178-181.
I don't know of existing implementations for either of these in Mathematica.
--
David Eppstein UC Irvine Dept. of Information & Computer Science
eppstein at ics.uci.edu http://www.ics.uci.edu/~eppstein/
==== [MESSAGE SEPARATOR] ====