Variations of largest rectangle recognition amidst a bichromatic point set

DOI10.1016/j.dam.2019.05.012zbMath1453.68198arXiv1905.07124OpenAlexW2951342081WikidataQ127664860 ScholiaQ127664860MaRDI QIDQ2201768

Minati De, Supantha Pandit, Ankush Acharyya, Subhas C. Nandy

Publication date: 17 September 2020

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

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

zbMATH Keywords

orthogonal range countingspace-efficient algorithmsbichromatic point setin-place \(k\)-\(d\) treemaximum-weight rectangle recognitionobstacle-free rectangle recognition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)

Related Items (2)

Dot to dot, simple or sophisticated: a survey on shape reconstruction algorithms ⋮ Separating bichromatic point sets in the plane by restricted orientation convex hulls

Cites Work

• Unnamed Item
• A new algorithm for the largest empty rectangle problem
• On the maximum empty rectangle problem
• The design of dynamic data structures
• Space-efficient geometric divide-and-conquer algorithms
• Separating bichromatic point sets by L-shapes
• Covering point sets with two disjoint disks or squares
• Computing circular separability
• Stable minimum space partitioning in linear time
• Mining for empty spaces in large data sets.
• Maximal empty coboids among points and blocks
• The maximum box problem and its application to data analysis
• Computing the maximum bichromatic discrepancy, with applications to computer graphics and machine learning
• Covering a bichromatic point set with two disjoint monochromatic disks
• An in-place min-max priority search tree
• Maximum-weight planar boxes in \(O(n^2)\) time (and better)
• Polynomial Time Algorithms for Bichromatic Problems
• Bichromatic separability with two boxes: A general approach
• The Mono- and Bichromatic Empty Rectangle and Square Problems in All Dimensions
• Efficient Colored Orthogonal Range Counting
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• Computing the Largest Empty Rectangle
• Multidimensional binary search trees used for associative searching
• Largest empty rectangle among a point set
• On Computing a Largest Empty Arbitrarily Oriented Rectangle
• Towards in-place geometric algorithms and data structures
• Maximal Empty Boxes Amidst Random Points

This page was built for publication: Variations of largest rectangle recognition amidst a bichromatic point set