Largest empty shapes

2026-05-11 · Source: Yet Another Math Programming Consultant · Field: Technology & Digital — Mathematics & Computational Sciences, Data Science & Analytics · Depth: Advanced, long

Summary

This post explores optimization problems focused on identifying the largest empty geometric shapes (squares, diamonds, rectangles, and circles) within a given set of 100 uniformly distributed data points on a 10x10 grid. It details the mathematical modeling and implementation using various solvers, including Mixed-Integer Programming (MIP), Mixed-Integer Second-Order Cone Programming (MISOCP), and Nonconvex Nonlinear Programming (NLP). For the largest empty square and diamond, MIP models are employed, maximizing side length or L1 distance, respectively. The largest empty rectangle problem is formulated as an MISOCP by maximizing the square root of the area, while the largest empty circle is a nonconvex NLP. The article also demonstrates finding the five largest distinct empty rectangles by iteratively solving the MISOCP model with added spatial separation constraints.

Key takeaway

For data scientists and operations researchers working with spatial optimization, understanding that different empty shape problems necessitate distinct mathematical programming approaches is crucial. You should select solvers based on the problem's convexity: MIP for linear, MISOCP for certain quadratic, and global NLP for inherently nonconvex challenges. This tailored approach ensures efficient and accurate solutions, especially when identifying optimal placements or "holes" in data distributions.

Key insights

Finding largest empty shapes in point sets requires diverse optimization models depending on the shape.

Principles

• Monotonic transformations simplify non-convex objectives.
• Big-M constraints enable disjunctions in MIP models.
• Convex relaxations are key for integer problems.

Method

The approach involves formulating high-level geometric problems into specific mathematical programming models (MIP, MISOCP, NLP) using techniques like binary variables for disjunctions, variable splitting for absolute values, and rotated second-order cone constraints for quadratic objectives.

In practice

• Use MIP for largest empty squares and diamonds.
• Employ MISOCP for largest empty rectangles.
• Utilize global NLP solvers for largest empty circles.

Topics

• Largest Empty Shapes
• Geometric Optimization
• Mixed-Integer Programming
• Second-Order Cone Programming
• Nonlinear Programming

Best for: Research Scientist, Data Scientist

Related on AIssential

• Revisiting a crazy global NLP problem — Non-convex quadratic optimization problems can be intractable even for small instances.
• Mixture models as math programming problem — Mathematical programming offers robust, flexible methods for mixture models, outperforming standard statistical heuristics in some cases.
• Amortizing Maximum Inner Product Search with Learned Support Functions — Amortized MIPS uses neural networks to predict optimal keys, exploiting the support function's convex and homogeneous properties.
• Different Layers, Different Manifolds: Module-Wise Weight-Space Geometry in Transformer Optimization — Transformer optimization benefits from module-specific manifold constraints, with Stiefel for attention and DGram for MLP layers.
• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums — SILAGE optimizes nested finite sums with ℮(n) memory and no global full-gradient refreshes, adapting to data heterogeneity.
• A Function-Centric Perspective on Flat and Sharp Minima — Sharpness in neural network minima is function-dependent, not solely indicative of poor generalization.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by Yet Another Math Programming Consultant.