Passer à la navigation principale Passer à la recherche Passer au contenu principal

Linear approximation of simple objects

  • University of Montreal
  • McGill University

Résultats de recherche: Chapitre dans un livre, rapport, actes de conférence › Participation à un ouvrage collectif lié à un colloque ou une conférence › Revue par des pairs

1 Citation (Scopus)

Résumé

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.

Langue originaleAnglais
titreSTACS 1992 - 9th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
rédacteurs en chefAlain Finkel, Matthias Jantzen
EditeurSpringer Verlag
Pages233-244
Nombre de pages12
ISBN (imprimé)9783540552109
Les DOIs
ÉtatPublié - 1992
Modification externeOui
Evénement9th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1992 - Cachan, France
Durée: 13 févr. 1992 → 15 févr. 1992

Série de publications

NomLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume577 LNCS
ISSN (imprimé)0302-9743
ISSN (Electronique)1611-3349

Conférence

Conférence9th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1992
Pays/TerritoireFrance
La villeCachan
Période13/02/92 → 15/02/92

Classification disciplinaire ASJC Scopus

  • Informatique théorique
  • Informatique générale

Empreinte digitale

Voici les principaux termes ou expressions associés à « Linear approximation of simple objects ». Ces libellés thématiques sont générés à partir du titre et du résumé de la publication. Ensemble, ils forment une empreinte digitale unique.

Citer cette ressource