| Optimization in Arrangements (2003) | |||||||||||||||||
Abstract | |||||||||||||||||
| Many problems can be formulated as the optimization of functions in R² which are implicitly defined by an arrangement of lines, halfplanes, or points, for example linear programming in the plane. We present an e#cient general approach to find the optimum exactly, for a wide range of functions that possess certain useful properties. To illustrate the value of this approach, we give a variety of applications in which we speed up or simplify the best known algorithms. These include algorithms for finding robust geometric medians (such as the Tukey Median), robust regression lines, and ham-sandwich cuts. | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||