On the coarseness of bicolored point sets

DSpace/Manakin Repository

On the coarseness of bicolored point sets

Show full item record

Title: On the coarseness of bicolored point sets
Author(s):
Bereg, Sergey;
Díaz-Báñez, J. M.;
Lara, D.;
Pérez-Lantero, P.;
Seara, C.;
Urrutia, J.
Date Created: 2010-11-10
Format: text
Item Type: Article
Keywords: Irregularities of distribution (Number theory)
Algorithms.
Red-blue separability
Computational geometry
Abstract: Let R be a set of red points and B a set of blue points on the plane. In this paper we introduce a new concept, which we call coarseness, for measuring how blended the elements of S=R⊃B are. For X∪S, let Δ(X)= ||X⊂R|-|X⊂B|| be the bichromatic discrepancy of X. We say that a partition Π={ S1, S2,⋯, Sk} of S is convex if the convex hulls of its members are pairwise disjoint. The discrepancy of a convex partition Π of S is the minimum Δ( Si) over the elements of Π. The coarseness of S is the discrepancy of the convex partition of S with maximum discrepancy. We study the coarseness of bicolored point sets, and relate it to well blended point sets. In particular, we show combinatorial results on the coarseness of general configurations and give efficient algorithms for computing the coarseness of two specific cases, namely when the set of points is in convex position and when the measure is restricted to convex partitions with two elements. © 2012 Elsevier B.V.
Publisher: Elsevier B. V.
Source: Computational Geometry: Theory and Applications
Persistent Link: http://dx.doi.org/10.1016/j.comgeo.2012.04.003
http://hdl.handle.net/10735.1/2407
Bibliographic Citation: Bereg, S., J. M. Díaz-Báñez, D. Lara, P. Pérez-Lantero, C. Seara, and J. Urrutia. 2013. "On the Coarseness of Bicolored Point Sets." Computational Geometry: Theory and Applications 46 (1): 65-77.
Terms of Use: ©2012 Elsevier B. V. All rights reserved.

Files in this item

Files Size Format View
ECS-SR-311902.96.pdf 188.8Kb PDF View/Open

This item appears in the following Collection(s)


Show full item record