Locating least-distant lines in the plane

✍ Scribed by Anita Schöbel

• Book ID: 104339577
• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 525 KB
• Volume: 106
• Category: Article
• ISSN: 0377-2217
• DOI: 10.1016/s0377-2217(97)00254-3

✦ Synopsis

In this paper we deal with locating a line in a plane. Given a set of existing facilities, represented by points in the plane, our objective is to find a straight line I minimizing the sum of weighted distances to the existing facilities, or minimizing the maximum weighted distance to the existing facilities, respectively. We show that for all distance measures derived from norms, one of the lines minimizing the sum objective contains at least two of the existing facilities. For the center objective we always get an optimal line which is at maximum distance from at least three of the existing facilities. If all weights are equal, there is an optimal line which is parallel to one facet of the convex hull of the existing facilities.