[Date Index]
[Thread Index]
[Author Index]
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**
| |