Algorithmic Solutions > LEDA > LEDA Guide > Geometry Algorithms > Extremal Circles

Extremal Circles

The functions discussed here are direct applications of Voronoi diagrams.

Smallest Enclosing Circle

The smallest enclosing circle for a set `L` of points is the circle with the smallest radius containing all points in `L`. Such a circle has at least two points in `L` on its boundary and its center lies on the furthest site Voronoi diagram of `L`.
The center is either a vertex of the furthest site Voronoi diagram (three vertices of `L` on its boundary) or lies on an edge (two sites on the boundary).

On the right you see a smallest enclosing circle of a set of 10 points in the plane. The picture is a screenshot from the program below.

Largest Empty Circle

The largest empty circle for a set `L` of points is the circle with the largest radius whose interior is void of points in `L` and whose center lies inside the convex hull of `L`. Such a circle has at least two points in `L` on its boundary and its center lies on the nearest site Voronoi diagram of `L`.
The center of the circle is either a vertex (three vertices of L on its boundary) or lies on an edge of the Voronoi diagram (two sites on the boundary).

On the right you see a largest circle of a set of 10 points in the plane. The picture is a screenshot from the program below.

All Empty Circles

LEDA also provides functions to compute the list `CL` of all enclosing (picture on the left) and all empty (picture on the right) circles passing through three or more points of `L`.

Example Program for Computing Extremal Circles

The following program computes the extremal circles and was used to generate all pictures above.

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

using namespace leda;

int main()
{
list<rat_point> L;
random_points_in_square(10,50,L);

rat_circle C;
//C=SMALLEST_ENCLOSING_CIRCLE(L);
//C=LARGEST_EMPTY_CIRCLE(L);

list<rat_circle> LC;
ALL_ENCLOSING_CIRCLES(L,LC);
//ALL_EMPTY_CIRCLES(L,LC);

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

rat_point p;
forall(p,L) W.draw_filled_node(p.to_point());
//W.draw_circle(C.to_circle(),red);
forall(C,LC) W.draw_circle(C.to_circle(),red);
W.read_mouse();
W.screenshot("extremal_circle");

return 0;
}	     ```

See also:

Data Types for 2-D Geometry

Windows and Panels

Minimum Width and Minimum Area Annuli

Curve Reconstruction

Geometry Algorithms

Geometry

GeoWin

Manual Entries

Manual Page of Geometry Algorithms

Please send any suggestions, comments or questions to leda@algorithmic-solutions.com
© Copyright 2001-2003, Algorithmic Solutions Software GmbH