PARTITIONING COLORED POINT SETS INTO MONOCHROMATIC PARTS

DOI10.1142/S0218195902000943zbMath1152.68666MaRDI QIDQ4818568

Adrian Dumitrescu, János Pach

Publication date: 29 September 2004

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

zbMATH Keywords

matching algorithmcolored point setsDavenport-Schinzel sequencepartitioning algorithm

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorics in computer science (68R05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Erd?s problems and related topics of discrete geometry (52C10)

Related Items (9)

Diverse partitions of colored points ⋮ On plane spanning trees and cycles of multicolored point sets with few intersections ⋮ Monochromatic partitioning of colored points by lines ⋮ Chromatic variants of the Erdős--Szekeres theorem on points in convex position. ⋮ Planar Bichromatic Bottleneck Spanning Trees ⋮ Computing the coarseness with strips or boxes ⋮ The balanced connected subgraph problem ⋮ On polygons enclosing point sets. II ⋮ On the intersection number of matchings and minimum weight perfect matchings of multicolored point sets

Cites Work

• Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• Applications of a semi-dynamic convex hull algorithm
• Counting triangle crossings and halving planes
• Extremal problems for geometric hypergraphs
• On the convex layers of a planar set
• A Combinatorial Problem Connected with Differential Equations
• Matching colored points in the plane: Some new results

This page was built for publication: PARTITIONING COLORED POINT SETS INTO MONOCHROMATIC PARTS