Covering problems with polyellipsoids: a location analysis perspective
From MaRDI portal
Abstract: In this paper we analyze the extension of the classical smallest enclosing disk problem to the case of the location of a polyellipsoid to fully cover a set of demand points in . We prove that the problem is polynomially solvable in fixed dimension and analyze mathematical programming formulations for it. We also consider some geometric approaches for the problem in case the foci of the polyellipsoids are known. Extensions of the classical algorithm by Elzinga-Hearn are also derived for this new problem. Moreover, we address several extensions of the problem, as the case where the foci of the enclosing polyellipsoid are not given and have to be determined among a potential set of points or the induced covering problems when instead of polyellipsoids, one uses ordered median polyellipsoids. For these problems we also present Mixed Integer (Non) Linear Programming strategies that lead to efficient ways to solve it.
Recommendations
- New exact algorithms for planar maximum covering location by ellipses problems
- Optimal coverage of convex regions
- scientific article; zbMATH DE number 2119696
- Computational algorithms for the optimum covering of plane domains by a prescribed number of ellipses
- Deterministic and stochastic global optimization techniques for planar covering with ellipses problems
Cites work
- Convex ordered median problem with \(\ell _p\)-norms
- Deterministic and stochastic global optimization techniques for planar covering with ellipses problems
- Efficient Algorithms for the (Weighted) Minimum Circle Problem
- Exact algorithms for handling outliers in center location problems on networks using \(k\)-max functions
- Generalized coverage: new developments in covering location models
- Geometrical properties of the symmetrical single facility location problem
- scientific article; zbMATH DE number 1803755 (Why is no real title available?)
- scientific article; zbMATH DE number 3759045 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 823069 (Why is no real title available?)
- scientific article; zbMATH DE number 3027356 (Why is no real title available?)
- Minimizing ordered weighted averaging of rational functions with applications to continuous location
- Note—On a Modified One-Center Model
- On a circle placement problem
- On a Multidimensional Search Technique and Its Application to the Euclidean One-Centre Problem
- On the generalization of Erdős-Vincze's theorem about the approximation of regular triangles by polyellipses in the plane
- Polyconics. I. Polyellipses and optimization
- Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions
- Revisiting several problems and algorithms in continuous location with \(\ell _\tau \) norms
- Semidefinite representation of the \(k\)-ellipse
- Support vector data description
- Technical Note—Location Theory, Dominance, and Convexity: Some Further Results
- The Weighted Euclidean 1-Center Problem
- Using Block Norms for Location Modeling
Cited in
(8)- New exact algorithms for planar maximum covering location by ellipses problems
- An elliptical cover problem in drone delivery network design and its solution algorithms
- scientific article; zbMATH DE number 2119696 (Why is no real title available?)
- The discrete ellipsoid covering problem: a discrete geometric programming approach
- On hub location problems in geographically flexible networks
- Fairness in maximal covering location problems
- Multi-type maximal covering location problems: hybridizing discrete and continuous problems
- The cooperative maximal covering location problem with ordered partial attractions
This page was built for publication: Covering problems with polyellipsoids: a location analysis perspective
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2028797)
