×

zbMATH — the first resource for mathematics

Separated matchings and small discrepancy colorings. (English) Zbl 1375.68159
Márquez, Alberto (ed.) et al., Computational geometry. XIV Spanish meeting on computational geometry, EGC 2011, dedicated to Ferran Hurtado on the occasion of his 60th birthday, Alcalá de Henares, Spain, June 27–30, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-34190-8/pbk). Lecture Notes in Computer Science 7579, 236-248 (2012).
Summary: Consider \(2n\) points in the plane in convex position, \(n\) points are red and \(n\) points are blue. Edges are straight line segments connecting points of different color. A separated matching is a geometrically non-crossing matching where all edges can be crossed by a line. Separated matchings are closely related to non-crossing, alternating paths. M. Abellanas et al. [Discrete Appl. Math. 93, No. 2–3, 141–148 (1999; Zbl 0929.05021)] and independently J. Kynčl et al. [Discrete Math. 308, No. 19, 4315–4321 (2008; Zbl 1168.05320)] constructed convex point sets allowing at most \(\frac{4}{3}n+O(\sqrt n)\) points on any non-crossing, alternating path. We give a class of configurations that contains at most \(\frac{4}{3}n+O(\sqrt n)\) points in any separated matching. We also present a coloring with constant discrepancy parameter where the number of points in the maximum separated matching is very close to \(\frac{4}{3}n\). When the dicrepancy is at most three we show that there are at least \(\frac{4}{3}n\) points in the maximum separated matching.
For the entire collection see [Zbl 1253.68016].
MSC:
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
52B55 Computational aspects related to convexity
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abellanas, M., García, J., Hernández, G., Noy, M., Ramos, P.: Bipartite embeddings of trees in the plane. Discrete Appl. Math. 93, 141–148 (1999) · Zbl 0929.05021 · doi:10.1016/S0166-218X(99)00042-6
[2] Abellanas, M., García, A., Hurtado, H., Tejel, J.: Caminos Alternantes. In: Proc. X Encuentros de Geometría Computacional, Sevilla, pp. 7–12 (June 2003) (in Spanish)
[3] Cibulka, J., Kynčl, J., Mészáros, V., Stolař, R., Valtr, P.: Hamiltonian Alternating Paths on Bicolored Double-Chains. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 181–192. Springer, Heidelberg (2009) · Zbl 1213.68435 · doi:10.1007/978-3-642-00219-9_18
[4] Cibulka, J., Kynčl, J., Mészáros, V., Stolař, R., Valtr, P.: Universal Sets for Straight-Line Embeddings of Bicolored-Graphs. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory. Springer (to appear) · Zbl 1272.05126 · doi:10.1007/978-1-4614-0110-0_8
[5] Hajnal, P., Mészáros, V.: Note on noncrossing alternating path in colored convex sets. Accepted to Discrete Mathematics and Theoretical Computer Science
[6] Kaneko, A., Kano, M.: Discrete geometry on red and blue points in the plane – a survey. In: Aronov, B., et al. (eds.) Discrete and Computational Geometry, Goodman-Pollack Festschrift. Algorithms Comb., vol. 25, pp. 551–570. Springer (2003) · Zbl 1079.52505 · doi:10.1007/978-3-642-55566-4_25
[7] Kynčl, J., Pach, J., Tóth, G.: Long alternating paths in bicolored point sets. Discrete Mathematics 308(19), 4315–4321 (2008) · Zbl 1168.05320 · doi:10.1016/j.disc.2007.08.013
[8] Mészáros, V.: An upper bound on the size of separated matchings. Electronic Notes in Discrete Mathematics, 633–638 (2011) · Zbl 1274.05385 · doi:10.1016/j.endm.2011.10.006
[9] Mészáros, V.: Separated matchings in colored convex sets (manuscript)
[10] Mészáros, V.: Separated matchings in convex point sets with small discrepancy, CRM Documents 8, Centre de Recerca Matemática, Bellaterra, Barcelona, pp. 217–220 (2011)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.