Rectangular p-Centers

More formally the problem can be defined as follows.

Given a finite set of points, compute a point set with such that the p-radius of ,

is minimized. We can interpret as the best approximation (with respect to the given metric) for with at most p points.

#include <CGAL/rectangular_p_center_2.h>

template < class ForwardIterator, class OutputIterator, class FT, class Traits >
OutputIterator	rectangular_p_center_2 ( ForwardIterator f, ForwardIterator l, OutputIterator o, FT& r, int p, Traits t = Default_traits)

computes rectilinear p-centers for the point set described by the range [f, l), sets r to the corresponding $$p-radius, writes the at most p center points to o and returns the past-the-end iterator of this sequence.

The geometric types and operations to be used for the computation are specified by the traits class parameter t. This parameter can be omitted if ForwardIterator refers to a point type from the 2D-Kernel. In this case a default traits class implementation is used.

Preconditions

1. Either: (if no traits parameter is given) Value type of ForwardIterator is Point_2<R> for some representation class R and FT is equivalent to R::FT,
2. Or: (if a traits parameter is specified) Traits satisfies the requirements stated in section ,
3. OutputIterator accepts the value type of ForwardIterator as value type,
4. the range [f, l) is not empty and
5. 2 $$ p $$ 4.

Implementation

p {2,3}

(n ·

Example

#include <CGAL/Cartesian.h>
#include <CGAL/Point_2.h>
#include <CGAL/point_generators_2.h>
#include <CGAL/rectangular_p_center_2.h>
#include <CGAL/IO/Ostream_iterator.h>
#include <CGAL/algorithm.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
using CGAL::set_pretty_mode;
using CGAL::rectangular_p_center_2;

typedef double                                   FT;
typedef CGAL::Cartesian< FT >                    R;
typedef CGAL::Point_2< R >                       Point;
typedef std::vector< Point >                     Cont;
typedef CGAL::Creator_uniform_2< FT, Point >     Creator;
typedef CGAL::Random_points_in_square_2< Point, Creator >
  Point_generator;
typedef CGAL::Ostream_iterator< Point, ostream > Ostream_iterator_point;

int main() {

  int number_of_points(10);
  int p(2);
  Ostream_iterator_point cout_ip(cout);
  set_pretty_mode(cout);

  Cont points;
  CGAL::copy_n(Point_generator(1),
               number_of_points,
               back_inserter(points));
  cout << "Generated Point Set:" << endl;
  copy(points.begin(), points.end(), cout_ip);

  Cont centers;
  FT p_radius;
  rectangular_p_center_2(
    points.begin(),
    points.end(),
    back_inserter(centers),
    p_radius,
    3);

  cout << "\n\n" << p << "-centers:" << endl;
  copy(centers.begin(), centers.end(), cout_ip);
  cout << "\n\n" << p << "-radius = " << p_radius << endl;

  return 0;
}