## CGAL::extremal_polygon_2

| advanced |

### Definition

The function extremal_polygon_2 computes a maximal k-gon that can be inscribed into a given convex polygon. The criterion for maximality and some basic operations have to be specified in an appropriate traits class parameter.

#include <CGAL/extremal_polygon_2.h>

template < class RandomAccessIterator, class OutputIterator, class Traits >

OutputIterator

extremal_polygon_2 (
| RandomAccessIterator points_begin, RandomAccessIterator points_end, int k, OutputIterator o, Traits t)

computes a maximal (as specified by t) inscribed k-gon of the convex polygon described by [points_begin, points_end), writes its vertices to o and returns the past-the-end iterator of this sequence.

Precondition:

1. the - at least three - points denoted by the range [points_begin, points_end) form the boundary of a convex polygon (oriented clock- or counterclockwise).
2. k t.min_k().

Requirement:

1. Traits is a model for ExtremalPolygonTraits_2.
2. Value type of RandomAccessIterator is Traits::Point_2.
3. OutputIterator accepts Traits::Point_2 as value type.

### See Also

CGAL::maximum_area_inscribed_k_gon_2
CGAL::maximum_perimeter_inscribed_k_gon_2
ExtremalPolygonTraits_2
CGAL::monotone_matrix_search

### Implementation

The implementation uses monotone matrix search [AKM+87] and has a worst case running time of O(k · n + n · logn), where n is the number of vertices in P.

| advanced |