Tutorial of the CGAL extension package for parametric search

Parametric Search Package: TutorialRene´ van Oostrum and Remco C. VeltkampApril 18, 2005This document is the tutorial of the CGAL extension package for parametric search. It gives an overviewof the parametric-search framework, and explains how to use it by describing implementations of severalapplications of parametric search. The full documentation of all classes and functions that are meant to becalled from user-code can be found in the reference manual.1llllllllllllllllllllllllllllllllllllllll1 IntroductionParametric search, the optimization technique by Megiddo [3], has always been regarded to be more oftheoretical than of practical value. We provide a framework for parametric search that makes implementingapplications of the technique considerably simpler, especially for sorting-based parametric search.Theoretical background, some observations regarding the use of Quicksort for sorting-based parametricsearch, and a discussion about the need for Cole’s optimization [2] can be found in our accompanyingpaper [6], see also [5].This document is organized as follows. In Section 2 we discuss the basic ideas of parametric search.In Section 3 we give an overview of the important classes of the framework, and we explain how weuse explicit template instantiation to be able to retain separate compilation. In Section 4 we show howto implement applications of sorting-based parametric search. As an illustration, we give the ...