Paper
The Continuous p-Dispersion Problem in Three Dimensions
Authors
Sanjay Manoj, Melkior Ornik
Abstract
The Continuous p-Dispersion Problem (CpDP) with boundary constraints asks for the placement of a fixed number of points in a compact subset of Euclidean space such that the minimum distance between any two points, as well as the points and the boundary of this compact set is maximized. This problem finds applications in facility placement, communication network design, sampling theory, and particle simulation; however, finding optimal solutions is NP-hard and existing algorithms focus on providing approximate solutions in two-dimensional space. In this paper, we introduce an almost-everywhere differentiable optimization model and global optimization algorithm for approximating solutions to the CpDP with boundary constraints in convex and non-convex polyhedra with respect to any metric in a three-dimensional Euclidean space. Our algorithm generalizes two-dimensional dispersion techniques to three dimensions by leveraging orientation, linear-algebraic projections for point-to-face distances, and a ray-casting procedure for point-in-polyhedron testing, enabling optimization in arbitrary convex and non-convex three dimensional polyhedra. We validate the proposed algorithm by comparing with analytical optima where available and empirical benchmarks, observing close agreement with optimal solutions and improvements over empirical benchmarks.
Metadata
Related papers
Fractal universe and quantum gravity made simple
Fabio Briscese, Gianluca Calcagni • 2026-03-25
POLY-SIM: Polyglot Speaker Identification with Missing Modality Grand Challenge 2026 Evaluation Plan
Marta Moscati, Muhammad Saad Saeed, Marina Zanoni, Mubashir Noman, Rohan Kuma... • 2026-03-25
LensWalk: Agentic Video Understanding by Planning How You See in Videos
Keliang Li, Yansong Li, Hongze Shen, Mengdi Liu, Hong Chang, Shiguang Shan • 2026-03-25
Orientation Reconstruction of Proteins using Coulomb Explosions
Tomas André, Alfredo Bellisario, Nicusor Timneanu, Carl Caleman • 2026-03-25
The role of spatial context and multitask learning in the detection of organic and conventional farming systems based on Sentinel-2 time series
Jan Hemmerling, Marcel Schwieder, Philippe Rufin, Leon-Friedrich Thomas, Mire... • 2026-03-25
Raw Data (Debug)
{
"raw_xml": "<entry>\n <id>http://arxiv.org/abs/2602.23548v1</id>\n <title>The Continuous p-Dispersion Problem in Three Dimensions</title>\n <updated>2026-02-26T23:04:51Z</updated>\n <link href='https://arxiv.org/abs/2602.23548v1' rel='alternate' type='text/html'/>\n <link href='https://arxiv.org/pdf/2602.23548v1' rel='related' title='pdf' type='application/pdf'/>\n <summary>The Continuous p-Dispersion Problem (CpDP) with boundary constraints asks for the placement of a fixed number of points in a compact subset of Euclidean space such that the minimum distance between any two points, as well as the points and the boundary of this compact set is maximized. This problem finds applications in facility placement, communication network design, sampling theory, and particle simulation; however, finding optimal solutions is NP-hard and existing algorithms focus on providing approximate solutions in two-dimensional space. In this paper, we introduce an almost-everywhere differentiable optimization model and global optimization algorithm for approximating solutions to the CpDP with boundary constraints in convex and non-convex polyhedra with respect to any metric in a three-dimensional Euclidean space. Our algorithm generalizes two-dimensional dispersion techniques to three dimensions by leveraging orientation, linear-algebraic projections for point-to-face distances, and a ray-casting procedure for point-in-polyhedron testing, enabling optimization in arbitrary convex and non-convex three dimensional polyhedra. We validate the proposed algorithm by comparing with analytical optima where available and empirical benchmarks, observing close agreement with optimal solutions and improvements over empirical benchmarks.</summary>\n <category scheme='http://arxiv.org/schemas/atom' term='math.OC'/>\n <published>2026-02-26T23:04:51Z</published>\n <arxiv:comment>14 pages, 17 figures, 4 tables</arxiv:comment>\n <arxiv:primary_category term='math.OC'/>\n <author>\n <name>Sanjay Manoj</name>\n </author>\n <author>\n <name>Melkior Ornik</name>\n </author>\n </entry>"
}