caa a22 4500 46907521X CHVBK 20180323132933.0 cr unu---uuuuu 170328e19920101xx s 000 0 eng 10.1007/BF02187823 doi (NATIONALLICENCE)springer-10.1007/BF02187823 Finding minimum area k -gons [Elektronische Daten] [David Eppstein, Mark Overmars, Günter Rote, Gerhard Woeginger] Given a setP ofn points in the plane and a numberk, we want to find a polygon with vertices inP of minimum area that satisfies one of the following properties: (1) is a convexk-gon, (2) is an empty convexk-gon, or (3) is the convex hull of exactlyk points ofP. We give algorithms for solving each of these three problems in timeO(kn 3). The space complexity isO(n) fork=4 andO(kn 2) fork≥5. The algorithms are based on a dynamic programming approach. We generalize this approach to polygons with minimum perimeter, polygons with maximum perimeter or area, polygons containing the maximum or minimum number of points, polygons with minimum weight (for some weights added to vertices), etc., in similar time bounds. Springer-Verlag New York Inc., 1992 Eppstein David Department of Computer Science, University of California, 92717, Irvine, CA, USA aut Overmars Mark Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508 TB, Utrecht, The Netherlands aut Rote Günter Institut für Mathematik, Technische Universität Graz, Kopernikusgasse 24, A-8010, Graz, Austria aut Woeginger Gerhard Institut für Mathematik, Technische Universität Graz, Kopernikusgasse 24, A-8010, Graz, Austria aut Discrete & Computational Geometry Springer New York 7/1(1992-01-01), 45-58 0179-5376 7:1<45 1992 7 454 https://doi.org/10.1007/BF02187823 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02187823 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Eppstein David Department of Computer Science, University of California, 92717, Irvine, CA, USA aut NATIONALLICENCE 700 1- Overmars Mark Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508 TB, Utrecht, The Netherlands aut NATIONALLICENCE 700 1- Rote Günter Institut für Mathematik, Technische Universität Graz, Kopernikusgasse 24, A-8010, Graz, Austria aut NATIONALLICENCE 700 1- Woeginger Gerhard Institut für Mathematik, Technische Universität Graz, Kopernikusgasse 24, A-8010, Graz, Austria aut NATIONALLICENCE 773 0- Discrete & Computational Geometry Springer New York 7/1(1992-01-01), 45-58 0179-5376 7:1<45 1992 7 454 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer