Anchored hyperplane location problems

DOI10.1007/S00454-002-0741-ZMaRDI QIDQ1404501zbMATH OpenOpenAlexFDO

Authors Anita Schöbel

Publication date 21 August 2003

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00454-002-0741-z

zbMATH Keywords

center problemhyperplane locationmedian problemrestricted location

Mathematics Subject Classification ID

Continuous location (90B85)

Review text

The paper considers a restricted version of a hyperplane location problem in \(\mathbb R^n\): The anchored hyperplane location problem consists of locating a hyperplane in \(\mathbb R^n\) that passes through a given set of points \(P\) while it minimizes at the same time the median objective or the center objective, respectively, with respect to a second set of points \(Q\). Assuming that distances are measured by a norm in \(\mathbb R^n\), and for the case of the median objective, it is shown that there always exists an optimal anchored hyperplane that passes through at least \(n-k\) affinely independent points in \(Q\) (\(k\) denotes the number of affinely independent points in \(P\)). For the case of the center objective, the existence of an optimal anchored hyperplane that is at maximum distance from at least \(n-k+1\) affinely independent points in \(Q\) is proven. Moreover, every optimal anchored hyperplane has the respective property if distances are measured by a smooth norm. It is noted that these results imply polynomial time enumeration-based algorithms for the computation of an optimal anchored hyperplane.

Recommendations

• Point location in arrangements of hyperplanes
• Dynamic point location in arrangements of hyperplanes
• scientific article; zbMATH DE number 849181
• A note on point location in arrangements of hyperplanes
• scientific article; zbMATH DE number 2065332
• Publication:4728245
• Eulerian location problems
• Approximation of solutions for location problems
• Location problem and inner product spaces
• On the multisource hyperplanes location problem to fitting set of points

Cited in

(8)

• The Chebyshev hyperplane optimization problem
• On the multisource hyperplanes location problem to fitting set of points
• Minmax-distance approximation and separation problems: geometrical properties
• Application of growth functions in the prediction of live weight of domestic animals
• Weighted Median of the Data in Solving Least Absolute Deviations Problems
• Locating an axis-parallel rectangle on a Manhattan plane
• Searching for a best least absolute deviations solution of an overdetermined system of linear equations motivated by searching for a best least absolute deviations hyperplane on the basis of given data
• Three points method for searching the best least absolute deviations plane

This page was built for publication: Anchored hyperplane location problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1404501)