Anchored hyperplane location problems (Q1404501)

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.