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.