Polynomial Time Algorithms for Bichromatic Problems

DOI10.1007/978-3-319-53007-9_2zbMath1485.68257arXiv1610.00300OpenAlexW2528293472MaRDI QIDQ2971630

Sayan Bandyapadhyay, Aritra Banik

Publication date: 7 April 2017

Published in: Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1610.00300

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Monochromatic partitioning of colored points by lines, Variations of largest rectangle recognition amidst a bichromatic point set

Cites Work

• Unnamed Item
• Conflict-free coloring of points on a line with respect to a set of intervals
• Strong conflict-free coloring for intervals
• A new algorithm for the largest empty rectangle problem
• On the maximum empty rectangle problem
• Plane bichromatic trees of low degree
• The maximum box problem and its application to data analysis
• Triangular range counting query in 2D and its application in finding \(k\) nearest neighbors of a line segment
• Bichromatic 2-center of pairs of points
• An Optimal Algorithm for Plane Matchings in Multipartite Geometric Graphs
• Choice Is Hard
• Bichromatic separability with two boxes: A general approach
• The Mono- and Bichromatic Empty Rectangle and Square Problems in All Dimensions
• On Approximating the Depth and Related Problems
• Computing the Largest Empty Rectangle
• Largest empty rectangle among a point set
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• Deterministic conflict-free coloring for intervals
• Online Conflict‐Free Coloring for Intervals