Anchored Hyperplane Location Problems
Citable Link (URL):http://resolver.sub.uni-goettingen.de/purl?gs-1/5712
The anchored hyperplane location problem is to locate a hyperplane passing through some given points P ⊆ Rn and minimizing either the sum of weighted distances (median problem), or the maximum weighted distance (center problem) to some other points Q ⊆ Rn . This problem of computational geometry is analyzed by using nonlinear programming techniques. If the distances are measured by a norm, it will be shown that in the median case there exists an optimal hyperplane that passes through at least n − k affinely independent points of Q, if k is the maximum number of affinely independent points of P. In the center case, there exists an optimal hyperplane which is at maximum distance to at least n −k +1 affinely independent points of Q. Furthermore, if the norm is a smooth norm, all optimal hyperplanes satisfy these criteria. These results generalize known results about unrestricted hyperplane location problems.