MathGroup Archive 1996

[Date Index] [Thread Index] [Author Index]

Search the Archive

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