Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6874178 | Information Processing Letters | 2018 | 5 Pages |
Abstract
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 present algorithms to find convex sets containing a balanced number of red and blue points. We provide an O(n4) time algorithm that for a given αâ[0,12] finds a convex set containing exactly âαrâ red points and exactly âαbâ blue points of S. If âαrâ+âαbâ is not much larger than 13n, we improve the running time to O(nlogâ¡n). We also provide an O(n2logâ¡n) time algorithm to find a convex set containing exactly âr+12â red points and exactly âb+12â blue points of S, and show that balanced islands with more points do not always exist.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Oswin Aichholzer, Nieves Atienza, José M. DÃaz-Báñez, Ruy Fabila-Monroy, David Flores-Peñaloza, Pablo Pérez-Lantero, Birgit Vogtenhuber, Jorge Urrutia,