Variations of largest rectangle recognition amidst a bichromatic point set

DOI10.1016/J.DAM.2019.05.012MaRDI QIDQ2201768zbMATH OpenOpenAlexWikidataFDO

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

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

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.

Recommendations

• Bichromatic separability with two boxes: A general approach
• Planar maximum-box problem revisited
• Geometric separability using orthogonal objects
• Polynomial time algorithms for bichromatic problems
• Fast sequential and parallel algorithms for finding the largest rectangle separating two sets

Cites work

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

Cited in

(3)

• Dot to dot, simple or sophisticated: a survey on shape reconstruction algorithms
• Separating bichromatic point sets in the plane by restricted orientation convex hulls
• Bichromatic separability with two boxes: A general approach

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)