## Abstract

Let S be a family of m convex polygons in the plane with a total number of n vertices and let each polygon have a positive weight associated with it. This paper presents algorithms to solve the weighted minmax approximation and the weighted minsum approximation problems. For the first problem, a line minimizing the maximum weighted orthogonal Euclidean distance to the polygons can be found in O(n^{2}logn) time and O(n^{2}) space. The time and space complexities can be reduced to O(n log n) and O(n), respectively, when the weights are equal. For the second problem, a line minimizing the sum of the weighted distances to the polygons can be found in O(nm log m) time and O(n) space. For both problems, we also consider constrained versions of these problems.

Original language | English (US) |
---|---|

Pages (from-to) | 27-52 |

Number of pages | 26 |

Journal | Computational Geometry: Theory and Applications |

Volume | 4 |

Issue number | 1 |

DOIs | |

State | Published - May 1994 |

## Keywords

- Dual transform
- Line sweep algorithms
- Linear approximation

## ASJC Scopus subject areas

- Computer Science Applications
- Geometry and Topology
- Control and Optimization
- Computational Theory and Mathematics
- Computational Mathematics