On the coarseness of bicolored point sets

dc.contributor.authorBereg, Sergeyen_US
dc.contributor.authorDíaz-Báñez, J. M.
dc.contributor.authorLara, D.
dc.contributor.authorPérez-Lantero, P.
dc.contributor.authorSeara, C.
dc.contributor.authorUrrutia, J.
dc.contributor.utdAuthorBereg, Sergey
dc.date.accessioned2012-11-26T19:55:38Z
dc.date.available2012-11-26T19:55:38Z
dc.date.created2010-11-10en_US
dc.date.issued2012-04-24en_US
dc.description.abstractLet 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)=en_US
dc.description.abstractX⊂R|-|X⊂Ben_US
dc.description.abstractbe 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.en_US
dc.description.versionFinal author's manuscript accepted for publicationen_US
dc.identifier.bibliographicCitationBereg, 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.en_US
dc.identifier.urihttp://hdl.handle.net/10735.1/2407
dc.publisherElsevier B. V.en_US
dc.relation.urihttp://dx.doi.org/10.1016/j.comgeo.2012.04.003
dc.relation.urihttp://dx.doi.org/10.1016/j.comgeo.2012.04.003en_US
dc.rights©2012 Elsevier B. V. All rights reserved.en_US
dc.sourceComputational Geometry: Theory and Applicationsen_US
dc.subjectComputational geometry
dc.subjectIrregularities of distribution (Number theory)en_US
dc.subjectAlgorithms.en_US
dc.subjectRed-blue separabilityen_US
dc.titleOn the coarseness of bicolored point setsen_US
dc.typetexten_US
dc.type.genrearticleen_US

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
ECS-SR-311902.96.pdf
Size:
188.83 KB
Format:
Adobe Portable Document Format

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
Bereg Submission and License Agreement.pdf
Size:
189.46 KB
Format:
Adobe Portable Document Format
Description:

Collections