Re: The farthest apart points problem

*To*: mathgroup at smc.vnet.net*Subject*: [mg4509] Re: The farthest apart points problem*From*: danl (Daniel Lichtblau)*Date*: Fri, 2 Aug 1996 02:22:37 -0400*Organization*: Wolfram Research, Inc.*Sender*: owner-wri-mathgroup at wolfram.com

In article <4t6b17$7d3 at dragonfly.wolfram.com> Riccardo Rigon <rigon at csrp.tamu.edu> 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 pairs is separated by the largest > distance ? > > Thank you in advance for any help, > > Riccardo > > I'll show an algorithm with O(n*log(n)) complexity, n being the number of points. I do not know whether this is optimal (and simplicity is in the eye of the beholder). The basic idea is to form explicitly the n-gon for this convex hull, and then use knowledge of who is neighbor to whom to find candidate maximally separated pairs. If you have the hull explicitly, that is, know the neighbors of each point, then it becomes O(n). (i) Pick a vertex v_0. Take distances from v_0 to all other points. Call a vertex that minimizes these distances (there are at most two such) v_0min. Call a maximizing vertex v_0max. (ii) One neighbor of v_0 is v0_min in the convex hull. Call lv0 the line between these neighbors. Form lines between v0 and all remaining n-2 vertices. Order these according to angle, measured counter-clockwise (CCW) from the ray emanating at v0, going through v_0min. This ordering gives the convex hull as an n-gon. Note that angle on this n-gon must strictly increase once we are off lv0. To handle colinearity it suffices to order those points with angle zero or pi by distance from v_0. (iii) Each vertex has one or two corresponding vertices at maximal distance from it (call these maximizing co-points). As one such pairing suffices, we have Ceiling(n/2) candidate pairs. Clearly v_0 and v_0max form one such pair. By convexity all other pairs have one point on each side of lv0 or else have v_0max as one vertex (exception that can be ignored: the other point, if such exists, that maximized distance from v_0). Moreover as we move over one point CCW from v_0 toward v_0max, the maximizer co-point moves CCW. We have found it once distances no longer increase. Let v_1 be the neighbor CCW from v_0. Take distance from v_1 to v_0max, to point immediately CCW from v_0max, to next point CCW, until distance no longer increases. This gives v_1max, the maximizing co-point for v_1. Let v_2 be the neighbor CCW from v_1. Take distance to v_1max, to point CCW from v_1max, etc. until distances no longer increase, and obtain v_2max. Continue in this fashion until we have maximizing co-points for all points up to v_0max. (iv) We have our candidate pairs. Find the biggest. Complexity: Steps (i), (iii), and (iv) are O(n). Step (ii) requires sorting n-2 values, hence can be done in O(n*log(n)). If there are many points and the angles formed with lv0 are reasonably well distributed between 0 and 180 in degrees, then a practical improvement might be to first sort the angles into buckets where most significant digit is zero, is one, ..., is 179, and then sort each bucket. The expected complexity is then O(n*log(n/180)). Note that step (iii) can be improved, and step (iv) removed, as follows. Continue (iii) so long as maximal pair distances increase. When they cease to do so, stop and your maximal distance is that of the last maximal pair found for which distances were increasing. If maximal pair distances are initially decreasing (that is, |v_0-v_0max| > |v_1 - v_1max|) then reverse direction and go clockwise instead. Daniel Lichtblau Wolfram Research, Inc. danl at wolfram.com ==== [MESSAGE SEPARATOR] ====