Algorithmic Solutions > LEDA > LEDA Guide > Geometry Algorithms > Width of a Point Set

## The Width of a Point Set

### What is the Width of a Point Set?

The width of a set `L` of points is the minimal stripe containing all points in `L`. A stripe is the region between two parallel lines.

The function

`	RAT_TYPE WIDTH(const list<POINT>& L, LINE& l1, LINE& l2)`

assumes that `L` is non-empty and returns the square of the minimum width of a stripe containing `L` and the boundaries of the stripe in `l1` and `l2`.

We use the notation `POINT (LINE) ` to indicate that the algorithm works both for `points(lines)` and ```rat_points (rat_lines). RAT_TYPE``` is double for the floating point kernel and `rational` for the rational kernel. See also Writing Kernel Independent Code.

The algorithm essentially computes the convex hull to compute the width of `L`.

Running Time: The asymptotic running time is the same as for computing the convex hull of `L`.

### Example

 The following program generates a ```list S``` of 100 `rat_points` in the square `(-50,-50,50,50)` and computes the width of `L`. Then it draws the points of `L` in black and the lines l1 and l2 in red. On the right there is a screenshot of the program. Clicking on the picture shows the `window` in original size.
```#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>

using namespace leda;

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

rat_line l1, l2;
rational w=WIDTH(L,l1,l2);

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

rat_point p;  //draw points in L
forall(p,L) {W.draw_filled_node(p.to_point());}

//draw l1 and l2 in red
W.draw_line(l1.to_line(),red);
W.draw_line(l2.to_line(),red);

W.screenshot("width");

return 0;
}	  ```

Linear Lists

Data Types for 2-D Geometry

Rational Numbers

Writing Kernel Independent Code

Windows and Panels

Geometry Algorithms

Geometry

GeoWin

Number Types

### Manual Entries

Manual Page of Geometry Algorithms