An optimal algorithm for plane matchings in multipartite geometric graphs

DOI10.1016/j.comgeo.2017.02.004zbMath1445.68241OpenAlexW2590962680MaRDI QIDQ1616235

Subhas C. Nandy, Ahmad Biniaz, Anil Maheshwari, Michiel H. M. Smid

Publication date: 1 November 2018

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2017.02.004

zbMATH Keywords

colored point setsbalanced cutplane matchings

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Unnamed Item
• Unnamed Item
• Balanced line for a 3-colored point set in the plane
• Balanced partitions of 3-colored geometric sets in the plane
• Maintenance of configurations in the plane
• Applications of a semi-dynamic convex hull algorithm
• Algorithms for ham-sandwich cuts
• The hamburger theorem
• Properly Colored Geometric Matchings and 3-Trees Without Crossings on Multicolored Points in the Plane
• Geometry Helps in Matching
• Buckets, Heaps, Lists, and Monotone Priority Queues
• Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications
• Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler

This page was built for publication: An optimal algorithm for plane matchings in multipartite geometric graphs