@inproceedings{216c6c7d425c4f3c9fc75a032aa769b5,

title = "Linear approximation of simple objects",

abstract = "Let S be a set of m convex polygons in the plane with a total number of n vertices. Each polygon has a positive weight. 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 distance to the polygons can be found in O(n2 log n) time and O(n2) 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(n2 log n) time and O(n) space. For both problems, we also obtain similar results for sets of n circles or line segments.",

author = "Robert, {Jean Marc} and Godfried Toussaint",

year = "1992",

doi = "10.1007/3-540-55210-3_187",

language = "English (US)",

isbn = "9783540552109",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "233--244",

editor = "Alain Finkel and Matthias Jantzen",

booktitle = "STACS 1992 - 9th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings",

note = "9th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1992 ; Conference date: 13-02-1992 Through 15-02-1992",

}