Abstract
It is shown that any two-colored set of n points in general position in the plane can be partitioned into at most \( \left\lceil {\tfrac{{n + 1}} {2}} \right\rceil \) monochromatic subsets, whose convex hulls are pairwise disjoint. This bound cannot be improved in general. We present an O(n log n) time algorithm for constructing a partition into fewer parts, if the coloring is unbalanced, i.e., the sizes of the two color classes differ by more than one. The analogous question for k-colored point sets (k > 2) and its higher dimensional variant are also considered.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
P. K. Agarwal, M. Sharir, and P. Shor, Sharp upper and lower bounds for the length of general Davenport-Schinzel sequences, Journal of Combinatorial Theory, Ser. A, 52 (1989), 228–274.
V. Aho, J. Hopcroft and J. Ullman, The Design and analysis of Computer Algorithms, Addison-Wesley, Reading, 1974.
B. Chazelle, On the convex layers of a planar set, IEEE Transactions on Information Theory, 31(4) (1985), 509–517.
H. Davenport and A. Schinzel, A combinatorial problem connected with differential equations, American Journal of Mathematics, 87 (1965), 684–694.
T. K. Dey and H. Edelsbrunner, Counting triangle crossings and halving planes, Discrete & Computational Geometry, 12 (1994), 281–289.
T. K. Dey and J. Pach, Extremal problems for geometric hypergraphs, Discrete & Computational Geometry, 19 (1998), 473–484.
A. Dumitrescu and R. Kaye, Matching colored points in the plane: some new results, Computational Geometry: Theory and Applications, to appear.
A. Dumitrescu and W. Steiger, On a matching problem in the plane, Workshop on Algorithms and Data Structures, 1999 (WADS’99). Also in: Discrete Mathematics, 211 (2000), 183–195.
S. Hart and M. Sharir, Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes, Combinatorica, 6 (1986), 151–177.
J. Hershberger and S. Suri, Applications of a semi-dynamic convex hull algorithm, BIT, 32 (1992), 249–267.
K. Mehlhorn, Data Structures and Algorithms 3: Multi-dimensional searching and Computational Geometry, Springer Verlag, Berlin, 1984.
K. Mulmuley, Computational Geometry-An Introduction through Randomized Algorithms, Prentice Hall, Englewood Cliffs, 1994.
J. O’Rourke, Art Gallery Theorems and Algorithms, Oxford University Press, New York, 1987.
M. Sharir and P. K. Agarwal. Davenport-Schinzel Sequences and Their Geometric Applications, Cambridge University Press, Cambridge, 1995.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dumitrescu, A., Pach, J. (2001). Partitioning Colored Point Sets into Monochromatic Parts. In: Dehne, F., Sack, JR., Tamassia, R. (eds) Algorithms and Data Structures. WADS 2001. Lecture Notes in Computer Science, vol 2125. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44634-6_25
Download citation
DOI: https://doi.org/10.1007/3-540-44634-6_25
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42423-9
Online ISBN: 978-3-540-44634-7
eBook Packages: Springer Book Archive