Skip to content
TheChatArchiveThe Chat Archive
chatgpt-4o-latest-20250326· OpenAIHugging Face LMArena Human Preference 140K

I would like to solve the packing problem of packing N equally-sized circles into a…

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with gpt-4.1-2025-04-14’s answer.
  1. 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.

  2. 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=15 circles, then use gradient-based optimization to maximize the differentiable radius computed by your max_nonoverlapping_radius function.


    🔧 High-Level Strategy:

    1. Parameterize the centers of the circles (shape (N, 2), with entries in [-1, 1]).
    2. Use projected or clipped gradient descent to ensure the centers remain inside the unit circle.
    3. Maximize the output radius of max_nonoverlapping_radius(), which is differentiable.
    4. Implement a simple neural net or just use the coordinates as learnable parameters.
    5. 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_radius is 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 via x = r cos(θ), y = r sin(θ) with r ∈ [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_radius must 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

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.