Algorithmic Solutions > LEDA > LEDA Guide > Geometry Algorithms > Minkowski Sums

## Closest Pairs

 The function ```RAT_TYPE CLOSEST_PAIR(list& 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.screenshot("closest_pair");

return 0;
}	     ```

Data Types for 2-D Geometry

Writing Kernel Independent Code

Windows and Panels

Geometry Algorithms

Geometry

Graphs and Related Data Types

GeoWin

Number Types