Anchored Hyperplane Location Problems

Abstract

The anchored hyperplane location problem is to locate a hyperplane passing through some given points P R n and minimizing either the sum of weighted distances (median problem ), or the maximum weighted distance (center problem ) to some other points Q R n . 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.