Linear approximation of simple objects

Jean Marc Robert, Godfried T. Toussaint

Research output: Contribution to journalArticlepeer-review


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(n2logn) 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(nm log m) time and O(n) space. For both problems, we also consider constrained versions of these problems.

Original languageEnglish (US)
Pages (from-to)27-52
Number of pages26
JournalComputational Geometry: Theory and Applications
Issue number1
StatePublished - May 1994


  • 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


Dive into the research topics of 'Linear approximation of simple objects'. Together they form a unique fingerprint.

Cite this