Placing Two Axis-Parallel Squares to Maximize the Number of Enclosed Points

DOI10.1142/S0218195915500156zbMath1352.68270OpenAlexW2291025091MaRDI QIDQ2792797

Partha P. Goswami, Sandip Das, Priya Ranjan Sinha Mahapatra

Publication date: 14 March 2016

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0218195915500156

zbMATH Keywords

dynamic programmingcomputational geometrystaircase\(k\)-enclosing problemmaximal enclosing problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Combinatorial complexity of geometric structures (52C45)

Cites Work

• Enclosing \(k\) points in the smallest axis parallel rectangle
• Covering many or few points with unit disks
• Covering point sets with two disjoint disks or squares
• Smallest \(k\)-point enclosing rectangle and square of arbitrary orientation
• On a circle placement problem
• Optimal placement of convex polygons to maximize point containment
• Offset-polygon annulus placement problems
• Iterated nearest neighbors and finding minimal polytopes
• On geometric optimization with few violated constraints
• Covering a bichromatic point set with two disjoint monochromatic disks
• Improved algorithms for placing undesirable facilities
• Translating a convex polygon to contain a maximum number of points.
• Finding k points with minimum diameter and related problems
• Bichromatic separability with two boxes: A general approach
• New Upper Bounds in Klee’s Measure Problem
• Static and Dynamic Algorithms for k-Point Clustering Problems

This page was built for publication: Placing Two Axis-Parallel Squares to Maximize the Number of Enclosed Points