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