Geometry-Aware MCTS for Extremal Problems in Combinatorial Geometry
Quick Answer
This paper shows that The Geometry-Aware Monte Carlo Tree Search (MCTS) framework significantly improves solutions for extremal problems in combinatorial geometry, reducing constraint checking complexity from O(n^3) to O(n^2).
Quick Take
This framework achieved new best-known results for five out of six problems, including configurations of size approximately 1.8n for Max-N3IL and 0.95n for the Smallest Complete Set problem.
Key Points
- Introduces Geometry-Aware MCTS to tackle combinatorial geometry extremal problems.
- Reduces constraint checking complexity from O(n^3) to O(n^2) for collinear point configurations.
- Achieves new best-known results for five out of six tested problems.
- Finds configurations of size approximately 1.8n for grids in Max-N3IL.
- Establishes new upper bounds of size roughly 0.95n for the Smallest Complete Set problem.
Paper Resources
📖 Reader Mode
~2 min readAbstract:We study certain extremal problems in combinatorial geometry that ask about configurations of points in an $n \times n$ grid that satisfy strict, global geometric constraints. Classical exact solvers suffer from combinatorial explosion for these types of problems, and standard reinforcement learning and transformer-based models struggle with the sparse reward "validity cliff" and quadratic token-consumption limits. To overcome these bottlenecks, we propose a Geometry-Aware Monte Carlo Tree Search (MCTS) framework. Our approach strictly enforces geometric constraints through incremental updates to the feasible action space. For constraints about collections of collinear points, like those that occur in the classic No-Three-in-Line problem (Max-N3IL), this mechanism reduces the constraint checking complexity from $O(n^3)$ to $O(n^2)$. To improve search efficiency, we exploit geometric symmetries in two ways: canonical pruning during node expansion to reduce the branching factor, and symmetric batch transitions to accelerate the discovery of promising configurations. We perform extensive experiments and establish new best-known computational results on five out of six of the problems that we considered. Notably, for Max-N3IL we find configurations of size roughly $1.8 n$ for grids of size $82 \le n \le 119$. For the Smallest Complete Set problem, we find configurations of size roughly $0.95 n$, providing new upper bounds within the tested grids. This work establishes Geometry-Aware MCTS as a highly adaptable framework for discovering novel configurations in combinatorial geometry.
| Subjects: | Artificial Intelligence (cs.AI); Computational Geometry (cs.CG); Machine Learning (cs.LG); Combinatorics (math.CO) |
| Cite as: | arXiv:2606.26399 [cs.AI] |
| (or arXiv:2606.26399v1 [cs.AI] for this version) | |
| https://doi.org/10.48550/arXiv.2606.26399 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Nathan Kaplan [view email]
[v1]
Wed, 24 Jun 2026 21:34:08 UTC (7,020 KB)
— Originally published at arxiv.org
Want this in your inbox every morning?
Daily brief at your local 8am — bilingual EN/中文, free.
More from arXiv cs.AI
See more →HOBA: Hierarchical On-Policy Bidding Agents for Adaptive Online Advertising
HOBA (Hierarchical On-policy Bidding Agents) is a novel hierarchical reinforcement learning framework that enhances online advertising bidding systems by improving adaptability and reducing hyperparameter tuning costs. It utilizes a for hyperparameter inference, a SARSA agent for expert model selection, and a dynamic expert pool for bid execution, achieving a +3.6% increase in target cost during large-scale deployment and outperforming state-of-the-art baselines on AuctionNet.