From: David Eppstein
Newsgroups: comp.soft-sys.math.mathematica
Subject: Re: The minimum spanning circle problem
Date: 29 Jul 1996 03:18:33 GMT
Riccardo Rigon 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@ics.uci.edu http://www.ics.uci.edu/~eppstein/
==============================================================================
From: j-waldby@glhpx11.cen.uiuc.edu (James Irl Waldby)
Newsgroups: comp.soft-sys.math.mathematica
Subject: Re: The farthest apart points problem
Date: 25 Jul 1996 14:44:21 GMT
Riccardo Rigon writes:
> Let us have n points in a plane being the vertices of a convex hull.
> Do you know a fast and simple algorithm to determine which pair
> is separated by the largest distance ?
Perhaps comp.graphics.algorithms newsgroup would be a more
appropriate venue for the question.
If the n points are listed in adjacency order, p0, p1 ...
solve this in O(n) time: Find point p0' most distant from
first point p0. The line p1,p1' crosses* p0,p0' and in
general the line pj,pj' crosses* pi,pi' if j=i+1, so as
you step through p1, p2, p3 ... finding p1', p2', p3' ... you never
need to back up in the list of points you look at to find pj'.
*That is, it either shares an endpoint (pj'==pi') or crosses.