Id: arxiv/2611.22578 Url: https://arxiv.org/abs/2611.22578 Tags: math.OC Score: 0 Title: Maximin Dispersion over Simple Polyhedral Domains: Strong NP-Completeness and Exact Algorithms Domain: math.OC Source: arxiv Authors: Linbin Li, Yong Xia, Zhuoyi Xu Reviews: 0 Subject: math.OC Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-11-17 Page: https://delphi.science/r/arxiv/2611.22578 In this paper, we prove that the decision version of weighted maximin dispersion over the unit $\ell_1$-ball with rational sites and positive rational weights is strongly NP-complete. The same holds for unweighted dispersion over full-dimensional integer simplices when the sites are exactly their vertices. Both reductions from Exact Cover by 3-Sets rely on a shared quadratic rigidity argument. We also give exact algorithms that run in polynomial time for every fixed dimension. For the simplex problem, a Voronoi decomposition yields rational optimal solutions. For the weighted $\ell_1$-ball…