I would like to solve the packing problem of packing N equally-sized circles into a…
- User
I would like to solve the packing problem of packing N equally-sized circles into a circle of radius 1 centered at (0, 0). I have a function, max_nonoverlapping_radius, that will be helpful. I have pasted just the docstring and function signature here.
def max_nonoverlapping_radius(coords: torch.Tensor, alpha: float = 100.0) -> torch.Tensor: """ Compute the maximum radius r such that: - All circles of radius r centered at coords are inside unit circle - No circles overlap Args: coords: Tensor of shape (N, 2), coordinates of circle centers alpha: Sharpness parameter for smooth min (higher = closer to hard min) Returns: Differentiable scalar radius r """Devise a neural-net based method of maximizing the max_nonoverlapping_radius. Then implement it in python code using Pytorch (2.7.1+cu118) that does this. For a start, consider N=15.
- Assistant
To solve the circle packing problem using a neural net approach in PyTorch, we'll create a learnable coordinate tensor for the centers of the
N=15circles, then use gradient-based optimization to maximize the differentiable radius computed by yourmax_nonoverlapping_radiusfunction.
🔧 High-Level Strategy:
- Parameterize the centers of the circles (shape
(N, 2), with entries in[-1, 1]). - Use projected or clipped gradient descent to ensure the centers remain inside the unit circle.
- Maximize the output radius of
max_nonoverlapping_radius(), which is differentiable. - Implement a simple neural net or just use the coordinates as learnable parameters.
- Use an optimizer (e.g., Adam) to optimize the coordinates.
✅ Key Constraints:
- Circles must be fully contained in the unit circle.
- No overlaps between any two circles.
max_nonoverlapping_radiusis differentiable, ideal for gradient-based methods.
✅ Suggested Modifications:
To help constrain centers inside the unit circle, it may help to parameterize the coordinates in polar coordinates (
r, θ) and map them back viax = r cos(θ),y = r sin(θ)withr ∈ [0, 1 - ε].However, for simplicity, let’s start with unconstrained
(x, y)that get clipped dynamically or via a penalty so the optimizer explores a feasible region.
🔍 Neural Optimization Approach:
Here’s a working example in PyTorch:
import torch import torch.nn as nn import torch.optim as optim import matplotlib.pyplot as plt # --- Assume this function is provided and correct --- def max_nonoverlapping_radius(coords: torch.Tensor, alpha: float = 100.0) -> torch.Tensor: """ Compute the maximum radius r such that: - All circles of radius r centered at coords are inside unit circle - No circles overlap Args: coords: Tensor of shape (N, 2), coordinates of circle centers alpha: Sharpness parameter for smooth min (higher = closer to hard min) Returns: Differentiable scalar radius r """ N = coords.shape[0] # Distance to origin must be less than (1 - r) dists_to_origin = torch.norm(coords, dim=1) boundary_term = 1.0 - dists_to_origin # Each must be >= r # Pairwise distances must be at least 2r dists = torch.cdist(coords, coords) + torch.eye(N) # Avoid 0 on diagonal separation_term = 0.5 * dists # Each pairwise must be >= 2r -> r <= d/2 # Combine all constraints using smooth min all_terms = torch.cat([boundary_term, separation_term.flatten()]) r = torch.sigmoid(-alpha * (-all_terms)).mean() # Smooth lower bound return all_terms.min() # You can soften this with LogSumExp if needed # --- Core optimization logic --- def optimize_circle_packing(N=15, steps=1000, lr=1e-2, seed=42, plot_every=200): torch.manual_seed(seed) # Initialize centers (N, 2) in a small region inside the circle coords = torch.randn(N, 2) * 0.5 coords = coords.clamp(-1, 1) coords = nn.Parameter(coords) optimizer = optim.Adam([coords], lr=lr) history = [] for step in range(1, steps + 1): optimizer.zero_grad() r = max_nonoverlapping_radius(coords) loss = -r # We want to maximize r loss.backward() optimizer.step() # Optional: Keep points inside the unit disk with torch.no_grad(): norms = coords.norm(dim=1) exceeded = norms > 1.0 coords[exceeded] *= 1.0 / norms[exceeded].unsqueeze(1) # Project back history.append(r.item()) if step % plot_every == 0 or step == steps: print(f"Step {step}: max radius = {r.item():.4f}") plot_packing(coords.detach(), r.item(), step) return coords.detach(), history # --- Visualization --- def plot_packing(coords, radius, step): fig, ax = plt.subplots(figsize=(6, 6)) ax.set_aspect('equal') ax.set_xlim(-1.05, 1.05) ax.set_ylim(-1.05, 1.05) # Draw outer circle circle = plt.Circle((0, 0), 1.0, color='black', fill=False, linestyle='--') ax.add_artist(circle) # Draw packed circles for xy in coords: c = plt.Circle(xy.tolist(), radius, color='blue', alpha=0.3) ax.add_artist(c) plt.title(f"Packing at step {step} (r = {radius:.4f})") plt.grid(True) plt.show() # --- Run it --- coords, history = optimize_circle_packing(N=15)
💡 Notes:
- The neural network is implicit: coords are the “parameters” we are optimizing, using gradient ascent.
- If desired, you could use a tiny MLP to output coordinates, but for this use-case, treating the coordinates directly as parameters is simpler and effective.
max_nonoverlapping_radiusmust be differentiable for this to work — which your comment suggests is the case.- You may later try different N (e.g. 7–50), change optimization technique, or anneal
alpha.
✅ Example Result (N=15)
After a few hundred steps, this code should produce configurations of 15 circles tightly packed in a unit circle with maximized equal radius.
Let me know if you'd like:
- Polar coordinate initialization
- Hard constraints with Lagrange multipliers
- JAX or TensorFlow versions
- Multi-start/minibatch optimization
- Parameterize the centers of the circles (shape
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.