TY - GEN
T1 - Linear approximation of simple objects
AU - Robert, Jean Marc
AU - Toussaint, Godfried
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1992.
PY - 1992
Y1 - 1992
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/84936647933
U2 - 10.1007/3-540-55210-3_187
DO - 10.1007/3-540-55210-3_187
M3 - Contribution to conference proceedings
AN - SCOPUS:84936647933
SN - 9783540552109
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 233
EP - 244
BT - STACS 1992 - 9th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
A2 - Finkel, Alain
A2 - Jantzen, Matthias
PB - Springer Verlag
T2 - 9th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1992
Y2 - 13 February 1992 through 15 February 1992
ER -