2015/10/07 by Oswin Aichholzer, Nieves Atienza, Aichholzer, Oswin +16
Computer Science · Engineering · #Advanced Numerical Analysis Techniques #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Optimization and Packing Problems #cs.CG
paper · pdf · doi:10.48550/arxiv.1510.01819
openalex publication_date 2015/10/07 · arxiv created 2018/06/07 · arxiv updated 2018/06/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Let S be a set of n points in general position in the plane, r of which are red and b of which are blue. In this paper we prove that there exist: for every α∈ [ 0,(1)/(2) ], a convex set containing exactly \lceil αr\rceil red points and exactly \lceil αb \rceil blue points of S; a convex set containing exactly \lceil (r+1)/(2) \rceil red points and exactly \lceil (b+1)/(2) \rceil blue points of S. Furthermore, we present polynomial time algorithms to find these convex sets. In the first case we provide an O(n4) time algorithm and an O(n2log n) time algorithm in the second case. Finally, if \lceil αr\rceil+\lceil αb\rceil is small, that is, not much larger than (1)/(3)n, we improve the running time to O(n log n).