Locating Dimensional Facilities in a Continuous Space

Many applications in data analysis such as regression, projective clustering, or support vector machines can be modeled as location problems in which the facilities to be located are not represented by points but as dimensional structures. Examples for one-dimensional facilities are straight lines, line segments, or circles while boxes, strips, or balls are two-dimensional facilities. In this chapter we discuss the location of lines and circles in the plane, the location of hyperplanes and hyperspheres in higher dimensional spaces and the location of some other dimensional facilities. We formulate the resulting location problems and point out applications in statistics, operations research and data analysis. We identify important properties and review the basic solution techniques and algorithmic approaches. Our focus lies on presenting a unified understanding of the common characteristics these problems have, and on reviewing the new findings obtained in this field within the last years.