Electronic Resource
Springer
Discrete & computational geometry
29 (NaN), S. 229-238
ISSN:
1432-0444
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. The anchored hyperplane location problem is to locate a hyperplane passing through some given points P \subseteq R n and minimizing either the sum of weighted distances (median problem ), or the maximum weighted distance (center problem ) to some other points Q \subseteq 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s00454-002-0741-z
|
Location |
Call Number |
Expected |
Availability |