The Width of a Point Set

What is the Width of a Point Set?

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());}
  W.read_mouse();
  
  //draw l1 and l2 in red
  W.draw_line(l1.to_line(),red);
  W.draw_line(l2.to_line(),red);
  W.read_mouse();

  W.screenshot("width");
 
  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

Geometry

GeoWin

Number Types

Manual Entries

Manual Page of Geometry Algorithms