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 Traits >
OutputIterator	CGAL_rectangular_p_center_2 ( ForwardIterator f, ForwardIterator l, OutputIterator o, Traits::FT& r, int p, const 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.

Precondition

1. If t is specified explicitly, Traits satisfies the requirements stated in section ,
2. Value type of ForwardIterator is Traits::Point_2 or - if t is not specified explicitly - CGAL_Point_2<R> for some representation class R,
3. OutputIterator accepts the value type of ForwardIterator as value type,
4. the range [f, l) is not empty and
5. 2 p 4.

Note

On compilers not supporting member function templates, the parameter ForwardIterator is fixed to vector<Point_2>::iterator and OutputIterator is fixed to back_insert_iterator<vector<Point_2>> where Point_2 is Traits::Point_2.

Implementation

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/copy_n.h>
#include <CGAL/IO/Ostream_iterator.h>
#include <iostream.h>
#include <vector.h>

typedef double                            FT;
typedef CGAL_Cartesian< FT >              R;
typedef CGAL_Point_2< R >                 Point_2;
typedef vector< Point_2 >                 Cont;
typedef CGAL_Random_points_in_square_2<
  Point_2,
  CGAL_Creator_uniform_2< FT, Point_2 > >
Point_generator;
typedef CGAL_Ostream_iterator< Point_2, ostream >
  Ostream_iterator_point;

int main() {

  int number_of_points( 10);
  int p( 2);
  Ostream_iterator_point cout_ip( cout);
  CGAL_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;
  CGAL_rectangular_p_center_2(
    points.begin(),
    points.end(),
    back_inserter( centers),
    p_radius,
    p);
  cout << "\n\n" << p << "-centers:" << endl;
  copy( centers.begin(), centers.end(), cout_ip);
  cout << "\n\n" << p << "-radius = " << p_radius << endl;

}