Closest Pairs

The function RAT_TYPE CLOSEST_PAIR(list<POINT>& L, POINT& r1, POINT& r2)

computes a pair of points r1, r2 in L with minimal Euclidean distance between r1 and r2 and returns the squared distance between r1 and r2. We use the notation POINT to indicate that the algorithm works both for points and rat_points. See also Writing Kernel Independent Code. RAT_TYPE is double for the floating point kernel and Rational for the rational kernel. On the right there is a screenshot of the program below. Clicking on the picture shows the window in original size.

Running Time

The running time is O(nlogn) where n is the number of input points.

Example

The following program generates ten random points in a square and then computes the closest pair. The result is displayed using a window.

#include <LEDA/core/list.h>
#include <LEDA/geo/rat_point.h>
#include <LEDA/geo/random_rat_point.h>
#include <LEDA/graphics/window.h>
#include <LEDA/geo/geo_alg.h>
#include <LEDA/numbers/rational.h>

using namespace leda;

int main()
{
  list<rat_point> L;
  random_points_in_square(10,100,L);
 
  rat_point r1,r2;
  rational r=CLOSEST_PAIR(L,r1,r2);

  window W;
  W.init(-110,110,-110);
  W.open(); W.display();
  W.set_node_width(2);

  rat_point p;
  forall(p,L) W.draw_filled_node(p.to_point());

  W.set_node_width(3);
  W.draw_filled_node(r1.to_point(),red);
  W.draw_filled_node(r2.to_point(),red);
  W.draw_segment(r1.to_point(),r2.to_point(),red);
  W.read_mouse();

  W.screenshot("closest_pair");

  return 0;
}	     

See also:

Data Types for 2-D Geometry

Writing Kernel Independent Code

Rational

Windows and Panels

Geometry Algorithms

Geometry

Graphs and Related Data Types

GeoWin

Number Types

Manual Entries

Manual Page of Geometry Algorithms