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.


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.

Picture of Width of a Point Set
#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.display();

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

  return 0;

See also:

Linear Lists

Data Types for 2-D Geometry

Rational Numbers

Writing Kernel Independent Code

Convex Hulls

Windows and Panels

Geometry Algorithms



Number Types

Manual Entries

Manual Page of Geometry Algorithms

Please send any suggestions, comments or questions to
© Copyright 2001-2003, Algorithmic Solutions Software GmbH