Computing optimal islands |
| |
| Authors: | C Bautista-Santiago D Lara |
| |
| Institution: | a Universidad Nacional Autónoma de México, Mexicob Departamento Matemática Aplicada II. Escuela Técnica Superior de Ingenieros. Camino de los Descubrimientos, s/n, 41092, Sevilla, Spainc Universidad de Valparaiso, Chiled Universidad de Sevilla, Spain |
| |
| Abstract: | Let S be a bicolored set of n points in the plane. A subset I of S is an island if there is a convex set C such that I=C∩S. We give an O(n3)-time algorithm to compute a monochromatic island of maximum cardinality. Our approach is adapted to optimize similar (decomposable) objective functions. Finally, we use our algorithm to give an O(logn)-approximation for the problem of computing the minimum number of convex polygons that cover a class region. |
| |
| Keywords: | Maximum convex polygon Classification Computational geometry Algorithms |
| 本文献已被 ScienceDirect 等数据库收录！ |
