Source-linked AI summary
Visual Diffusion Models are Geometric Solvers
Nir Goren, Shai Yehezkel, Omer Dahary, Andrey Voynov, Or Patashnik, Daniel Cohen-Or
TL;DR
The Inscribed Square Problem remains unsolved for general curves, and hard geometric problems can have diverse solutions. The paper trains visual diffusion to generate geometric solution images and presents a shared framework across three case studies, without claiming to outperform specialized solvers.
Problem
The Inscribed Square Problem remains unsolved for general curves, and its multiple, often very different solutions are non-trivial to enumerate.
Source: §1 · p. 2Method
Results
Across three geometric case studies, the paper demonstrates image-space diffusion as a shared solver framework, without claiming it outperforms specialized solvers.
Source: §6 · p. 8Takeaways & Limitations
The authors suggest image-space diffusion may apply to a wider spectrum of geometric challenges beyond the three studied.
Source: §6 · p. 8The method uses finite-precision discretization; for Steiner trees, small perturbations preserve topology under general input assumptions, and quantized-vertex length estimates converge as the grid step decreases.
Source: §6 · p. 8
Abstract
from arXiv · showhide
In this paper we show that visual diffusion models can serve as effective geometric solvers: they can directly reason about geometric problems by working in pixel space. We first demonstrate this on the Inscribed Square Problem, a long-standing problem in geometry that asks whether every Jordan curve contains four points forming a square. We then extend the approach to two other well-known hard geometric problems: the Steiner Tree Problem and the Simple Polygon Problem. Our method treats each problem instance as an image and trains a standard visual diffusion model that transforms Gaussian noise into an image representing a valid approximate solution that closely matches the exact one. The model learns to transform noisy geometric structures into correct configurations, effectively recasting geometric reasoning as image generation. Unlike prior work that necessitates specialized architectures and domain-specific adaptations when applying diffusion to parametric geometric representations, we employ a standard visual diffusion model that operates on the visual representation of the problem. This simplicity highlights a surprising bridge between generative modeling and geometric problem solving. Beyond the specific problems studied here, our results point toward a broader paradigm: operating in image space provides a general and practical framework for approximating notoriously hard problems, and opens the door to tackling a far wider class of challenging geometric tasks.
1. introduction
The paper reframes diffusion as a way to solve hard geometric problems directly in pixel space. It uses the Inscribed Square Problem as a central case and extends the approach to other hard geometric tasks.
1. introduction
- The method treats geometric challenges as image-generation tasks, using diffusion sampling to discover structures guided by pixel-level formulations.This shifts diffusion from creative generation toward geometric problem solving.Source: §1 · p. 1
- Unlike diffusion approaches using symbolic or graph-based representations, this method represents geometric problems as images and reasons directly in pixel space.The paper contrasts its visual formulation with approaches to combinatorial problems such as TSP.Source: §1 · p. 2
- The Inscribed Square Problem remains unsolved for general curves, and a curve may have multiple very different squares that are non-trivial to enumerate.The paper uses distinct random seeds to uncover diverse valid squares.Source: §1 · p. 2
- The approach is demonstrated on the Steiner Tree Problem and the maximum-area Simple Polygon Problem, both described as NP-hard.Finite-resolution discretization limits the representation, while enabling valid approximations that can be refined.Source: §1 · p. 2
- Training generates a distribution of valid solution images and teaches diffusion to denoise Gaussian samples into that distribution, without elaborate encodings or specialized representations.The authors argue that constructing valid solution examples can be easier than deriving a solution for a specific instance; they propose applying the formulation to other hard problems with natural visual representations.Source: §1 · p. 2
2. Related Work
Prior diffusion solvers often operate on symbolic, graph-based, or parametric representations; other approaches use pixel-space images with additional optimization or specialized sampling. The cited methods illustrate these contrasting design choices.
2. Related Work
- DIFUSCO represents NP-complete problems as binary indicator vectors and learns a graph denoiser, while T2T learns high-quality solution distributions and uses gradient-guided test-time optimization.Fast T2T uses an optimization-consistency objective for single-step generation plus one gradient step [28].Source: §2 · p. 2
- A pixel-space TSP method uses an unconditional diffusion prior, then optimizes a parametric solution for each new instance with stochastic optimization and a differential renderer.The paper contrasts this with its conditional model, which generates solutions through DDIM sampling.Source: §2 · p. 2
- Figure 3 tracks square x0 predictions from t=T to t=0 across seed-specific rows, then shows the rigidly snapped t=0 prediction.At t=0, the figure also shows square edges and the minimum-area bounding box.Source: Figure 3 · p. 3
- A pixel-space Sudoku method assigns noise levels to patches and samples them in a learned or hand-crafted order, finding that sampling order matters relative to a fully parallel conditional DDPM baseline.Source: §2 · p. 3
3. Inscribed Square Problem
The inscribed-square case study uses conditional diffusion in pixel space to generate squares on Jordan curves, then evaluates their geometric validity and alignment.
3. Inscribed Square Problem
- The question of whether every Jordan curve contains an inscribed square remains open generally; prior algorithms target discrete or polygonal curves, unlike this pixel-space formulation.The conjecture has been established in several restricted curve settings.Source: §3 · p. 3
- Training pairs rasterized 128 × 128 smooth Jordan curves with inscribed squares; a U-Net conditions on the clean curve while denoising noisy square images.Each example pairs a curve image with one inscribed square.Source: §3 · pp. 3–4
- A coarse grid search over small rotations and translations maximizes negative mean corner-to-curve distance, nudging predicted squares closer to the curve.The alignment score is the negative average Euclidean distance from square vertices to the curve.Source: §3 · p. 4
- Evaluation reports curve alignment and square-likeness before snapping, after snapping, and for ground truth, separating generation from refinement.The paper avoids matching predictions to a single ground-truth square because curves may admit multiple valid squares.Source: §3 · p. 4
- Predicted squares closely approximate inscribed squares after snapping; Figure 4 shows examples, with residual deviations attributed to pixel-domain discretization.The paper notes that discretization also bounds ground-truth results.Source: Figure 4 · p. 4, §3 · p. 5
4. Steiner Tree Problem
The Euclidean Steiner Tree Problem seeks a minimum-length network connecting terminals, and the paper applies image-space diffusion to generate approximate solutions. The model often produces high-quality trees beyond its training range, though some outputs are invalid, especially for larger instances.
4. Steiner Tree Problem
- The Euclidean Steiner Tree Problem seeks a minimum-length network connecting terminals, may use additional Steiner points, and is NP-hard in the plane.A fixed-dimension PTAS nevertheless computes a (1+ε)-approximate tree in polynomial time for fixed ε.Source: §4 · p. 5
- Training uses GeoSteiner solutions for random instances with 10–20 points, rasterizes them, and conditions a U-Net diffusion model on terminal-point images.Edges, nodes, and background use different grayscale values; terminal points are concatenated with the noisy input at each denoising step.Source: §4 · p. 6
- The model’s image is decoded into a graph by detecting nodes and retaining candidate edges with sufficient foreground-pixel support.The implementation uses a 70% threshold for candidate edges and resolves some overlapping-edge ambiguities by retaining the shortest candidate.Source: §4 · p. 6
- Evaluation checks tree validity and terminal coverage, then selects the shortest valid output among 10 seeds; Table 2 compares validity and length ratios with random trees and MSTs.Test sets include 10–20 points, matching training, and ranges extending to 41–50 points.Source: §4 · p. 6, Table 2 · p. 6
- The model produces high-quality solutions for instances with more input points than seen in training and often aligns with the optimal trees.Figure 7 compares optimal and generated solutions visually.Source: §4 · p. 6, Figure 7 · p. 6
- Different noise seeds can yield varied solutions, and some outputs—especially on larger instances—are invalid because they contain loops.The third row of Figure 6 shows a loop, so the resulting graph is not a tree.Source: Figure 6 · p. 5, §4 · p. 6
5. Maximum Area Polygon Problem
The Maximum Area Polygonization Problem asks for a largest-area simple polygon through given points. The paper trains a conditional visual diffusion model on optimal polygon images; valid outputs are often near-optimal, while larger point sets pose greater validity challenges.
5. Maximum Area Polygon Problem
- The task is to find a non-self-intersecting polygon without holes that passes through every input vertex and has maximum area.The paper describes this as the Maximum Area Polygonization Problem.Source: §5 · pp. 6–7
- Training uses randomly sampled point sets and exhaustively searches valid simple polygons for optima, rasterizing polygons and conditioning the same U-Net architecture on input-point images.The exhaustive search uses a depth-first-search procedure and is feasible at the training scale.Source: §5 · p. 7
- At inference, candidate edges are extracted from foreground pixels, checked for intersections, and assembled into a simple cycle through all input vertices.The method retains edges with more than 70% pixel alignment and selects the largest-area valid candidate from 10 random seeds.Source: §5 · p. 7
- Evaluation covers the training range of 7–12 points and a 13–15-point generalization set, reporting validity, area ratios, and exact-optimum frequency against random polygons.Table 3 summarizes these metrics across input-point ranges.Source: §5 · p. 7, Table 3 · p. 7
- The generated polygons often align with optimal solutions, but validity drops noticeably on test instances with 13–15 points.Typical failures include missing input vertices or polygons with holes.Source: §5 · p. 7, Table 3 · p. 7
- Whenever the model produces a valid polygon, its area is typically very close to the optimum.Figure 8 shows examples where areas lost in one region are often balanced by areas gained elsewhere.Source: Figure 8 · p. 7, §5 · p. 8
6. Discussion and Conclusions
The paper presents visual diffusion as one simple framework for approximating hard geometric problems, while explicitly not claiming superiority to specialized solvers. Its experiments suggest accurate, diverse approximations and generalization, with finite precision and the 2D evaluation scope as important boundaries.
6. Discussion and Conclusions
- The same diffusion architecture applies across diverse problems, varying only task-specific training data and minimal decoding; the paper does not claim it outperforms specialized solvers.Carefully designed problem-specific algorithms may be more efficient or accurate.Source: §6 · p. 8
- The approach produces accurate, diverse approximations and can recover multiple valid solutions, as shown for the Inscribed Square Problem.The solutions can be refined further if desired.Source: §6 · p. 8
- Finite precision constrains the representation, but the authors argue that stability properties typically preserve solution structure and make quantized lengths converge as grid step decreases.For Steiner trees, topology is invariant to small perturbations of terminal vertices under general input assumptions.Source: §6 · p. 8
- Models trained on simpler instances generalize to larger inputs, and inference time remains constant with input size, unlike classical solvers that scale polynomially or exponentially.Source: §6 · p. 8
- Across tasks, early denoising steps reveal global solution structure and later steps refine it, suggesting more sampling budget could be shifted earlier with a small precision trade-off.The authors identify denoising schedulers as a possible way to optimize inference time.Source: §6 · p. 8
- The experiments focus on 2D; whether similar efficiency is achievable in 3D remains future work, potentially using volumetric or video-based models.Source: §6 · p. 8
7. Implementation Details
The implementation generates valid geometric-solution images for four problem components, then trains a conditional diffusion model to denoise them. Curve validity, discrete square refinement, and exact or solver-based solution generation provide the training data across the tasks.
7. Implementation Details
- The implementation details cover curve generation and square refinement, solution-instance generation for Steiner trees and maximum-area polygons, model architecture, and training.The paper presents this pipeline as a deliberately simple image-space strategy: train denoising on a distribution of valid solutions.Source: §7 · p. 11
7.1. Curve Generation
- Harmonic radial profiles are corrected with a periodic cubic spline so the curve passes through all four square vertices, then regenerated until it is a non-self-intersecting Jordan curve.The curve and square are translated and normalized before rasterization; Figure 10 illustrates the fitting and final curve.Source: §7.1 · p. 11, Figure 10 · p. 12
7.2. Square Enhancement
- For square enhancement, the method rigidly transforms an extracted square over a discrete rotation-and-translation grid and selects the transform with the best curve-alignment score.Translations are sampled in one-pixel steps; candidate masks are warped and scored against the curve.Source: §7.2 · p. 11
7.3. Steiner Tree Generation
- Steiner-tree instances sample 10–20 terminals, solve each with GeoSteiner, and rasterize the resulting trees into a dataset of 1,000,000 images.The images are 128×128 pixels, with terminals and Steiner points shown as black circles and edges as white lines.Source: §7.3 · p. 11
7.4. Maximum Area Polygon Generation
- Maximum-area polygon instances use exhaustive backtracking with geometric pruning to find the largest valid polygon, with the stated practical runtime applying to small sets of at most 15 points.The generated dataset contains 1,000,000 rasterized instances.Source: §7.4 · p. 11
7.5. Model Architecture
- The conditional U-Net uses a noisy target and condition image to predict a denoised single-channel output, with attention and residual blocks across its encoder and decoder.It has four encoder and decoder levels, channel progression 64 → 128 → 256 → 512, and attention at the bottleneck and levels 2 and 3.Source: §7.5 · pp. 11–12
7.6. Training Procedure
- Training uses DDIM with 100 steps and deterministic sampling, optimizing an L2 loss to predict noise added to the clean image.The training runs for 100 epochs with AdamW and a learning rate of 6×10−4, distributed across four GPUs.Source: §7.6 · p. 12
8. Additional Experiments
The additional experiments test geometric accuracy beyond rasterized images, compare diffusion with direct regression, and evaluate against prior learning-based solvers. They report a task-dependent trade-off: prior methods are competitive on maximum-area polygons, while the visual approach yields closer-to-optimal Steiner trees with reduced validity at higher point counts.
8. Additional Experiments
- The additional experiments assess rasterization error, compare diffusion with a regression baseline, and compare the approach with prior learning-based methods on maximum-area polygons and Steiner trees.The regression comparison uses identical training data and budget for the two models.Source: §8 · p. 12, §8.2 · p. 13
8.1. Parametric Evaluation for Inscribed Squares
- In parametric evaluation, predictions retain similar relative performance to the ground-truth raster upper bound, and snapping improves alignment in both pixel and parametric space.The comparison measures geometric accuracy using continuous square corners and the original polyline curve, alongside rasterized-image metrics.Source: §8.1 · p. 12, Table 4 · p. 13
8.2. Regression Model Ablation
- Direct regression often produces blurry or incomplete polygons that impede valid-polygon extraction, while its valid Steiner trees have length ratios comparable to diffusion but fail on most complex instances.The regression baseline uses the same U-Net backbone, training data, and budget, and outputs a solution image in one pass.Source: §8.2 · p. 13, Table 6 · p. 13
8.3. Comparison with Learning-Based Methods
- On maximum-area polygons, DIFUSCO performs slightly better with comparable validity; on Steiner trees, the approach is substantially closer to optimal than DeepSteiner, but validity falls at higher point counts.DIFUSCO uses a domain-specific architecture and does not extend to the Inscribed Square or Steiner Tree problems, whereas the visual model handles all three identically.Source: §8.3 · pp. 13–14, Table 8 · p. 14