Minmax-distance approximation and separation problems: geometrical properties

• 成果类型: Article
• 署名作者: Plastria, Frank; Carrizosa, Emilio
• 署名单位: Vrije Universiteit Brussel; University of Sevilla
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-010-0387-1
• 发表日期: 2012
• 页码: 153-177
• 关键词: linear facility location; plane; hyperplanes; points; circle

摘要

A center hyperplane in the d-dimensional space minimizes the maximum of its distances from a finite set of points A with respect to possibly different gauges. In this note it is shown that a center hyperplane exists which is at (equal) maximum distance from at least d + 1 points of A. Moreover the projections of the points among these which lie above the center hyperplane cannot be separated by another hyperplane from the projections of those that are below it. When all gauges involved are smooth, all center hyperplanes satisfy these properties. This geometric property allows us to improve and generalize previously existing results, which were only known for the case in which all distances are measured using a common norm. The results also extend to the constrained case where for some points it is prespecified on which side of the hyperplane (above, below or on) they must lie. In this case the number of points lying on the hyperplane plus those at maximum distance is at least d + 1. It follows that solving such global optimization problems reduces to inspecting a finite set of candidate solutions. Extensions of these results to a separation problem are outlined.