Re: The farthest apart points problem
- To: mathgroup at smc.vnet.net
- Subject: [mg4512] Re: The farthest apart points problem
- From: danl (Daniel Lichtblau)
- Date: Fri, 2 Aug 1996 02:22:39 -0400
- Organization: Wolfram Research, Inc.
- Sender: owner-wri-mathgroup at wolfram.com
In article <4t899l$h9m at dragonfly.wolfram.com> danl at wolfram.com (Daniel Lichtblau) writes: > 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 > > Thanks go to Bruce Alan Fast <Bruce.Fast at Colorado.EDU> for pointing out (in e-mail) that step (i) is already wrong. For a simple counter-example, imagine the four vertices of a long skinny diamond. The two points across the skinny axis will be closest to one another, but will not be neighbors on the convex hull. So let me try (i) again, this time using a method similar to that of step (ii). For each ray from v_0 to another vertex, find the angle, measured CCW, from the positive horizontal ray emanating from v_0. These angles will lie between 0 and 2*pi. Sort the remaining n-1 vertices according to these angles. This is O(n*log(n)). The two neighbors to v_0 will be adjacent in this sorting, and straddle a gap of at least pi (and obviously at most one pair does this even in the non-convex case); finding this gap is an O(n) search. Danl ==== [MESSAGE SEPARATOR] ====