Variations of largest rectangle recognition amidst a bichromatic point set

DOI10.1016/J.DAM.2019.05.012zbMATH Open1453.68198arXiv1905.07124OpenAlexW2951342081WikidataQ127664860 ScholiaQ127664860MaRDI QIDQ2201768FDOQ2201768

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

Publication date: 17 September 2020

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

Abstract: Classical separability problem involving multi-color point sets is an important area of study in computational geometry. In this paper, we study different separability problems for bichromatic point set P=P_rcup P_b on a plane, where $P_r$ and $P_b$ represent the set of n red points and m blue points respectively, and the objective is to compute a monochromatic object of the desired type and of maximum size. We propose in-place algorithms for computing (i) an arbitrarily oriented monochromatic rectangle of maximum size in R^2, (ii) an axis-parallel monochromatic cuboid of maximum size in R^3. The time complexities of the algorithms for problems (i) and (ii) are O(m(m+n)(msqrt{n}+mlog m+n log n)) and O(m^3sqrt{n}+m^2nlog n), respectively. As a prerequisite, we propose an in-place construction of the classic data structure the k-d tree, which was originally invented by J. L. Bentley in 1975. Our in-place variant of the $k$-d tree for a set of n points in R^k supports both orthogonal range reporting and counting query using O(1) extra workspace, and these query time complexities are the same as the classical complexities, i.e., O(n^{1-1/k}+mu) and O(n^{1-1/k}), respectively, where mu is the output size of the reporting query. The construction time of this data structure is O(nlog n). Both the construction and query algorithms are non-recursive in nature that do not need O(log n) size recursion stack compared to the previously known construction algorithm for in-place k-d tree and query in it. We believe that this result is of independent interest. We also propose an algorithm for the problem of computing an arbitrarily oriented rectangle of maximum weight among a point set P=P_r cup P_b, where each point in P_b (resp. P_r) is associated with a negative (resp. positive) real-valued weight that runs in O(m^2(n+m)log(n+m)) time using O(n) extra space.

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) Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

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

Cited In (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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2201768)