       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] ====

```

• Prev by Date: Re: Questions on the finer points.
• Next by Date: Re: bar charts with error bars?
• Previous by thread: The minimum spanning circle problem
• Next by thread: product of Spher.Harmonics