Inner and outer approximations of polytopes using boxes.
type: Item
instance of: scholarly article
title: Inner and outer approximations of polytopes using boxes.
zbMATH Open document ID: 1044.65016
DOI: 10.1016/S0925-7721(03)00048-8
author: Fabio D. Torrisi
author: A. Bemporad
author: Carlo Filippi
published in: Computational Geometry
publication date: 2004-03-14T00:00:00Z
review text: Die Autoren behandeln im euklidischen Raum \(\mathbb{R}^d\) (der auf ein kartesisches Koordinatensystem bezogen wird) die Innen- und Außenapproximation eines volldimensionalen, beschränkten, konvexen Polytops \({\mathcal P}\) durch volldimensionale Boxen. Boxen sind konvexe Polytope, deren definierende Hyperebenen zu den Koordinatenachsen parallel sind. Das Polytop \({\mathcal P}\) wird durch ein System linearer Ungleichungen gegeben. Eine Innenapproximation von \({\mathcal P}\) erfolgt durch eine Boxenmenge \({\mathcal J}\), eine Außenapproximation durch eine Boxenmenqe \({\mathcal E}\). Die zentrale Absicht besteht darin, Methoden anzugeben und zu testen, mit denen der bei einer Approximation entstehende Volumenfehler und zugleich die Gesamtzahl der verwendeten Boxen minimiert werden. Es wird versucht, eine gute Ausgewogenheit zwischen diesen gegensätzlichen Forderungen zu erzielen. Dafür werden insgesamt 7 Approximationsalgorithmen bereitgestellt und damit gemachte Computererfahrungen präsentiert. Die Grundidee besteht darin, ausgehend von einer Startbox rekursiv vorzugehen, die beiden Forderungen möglichst zu trennen und einen Rekursionsraum zu erzeugen. Die Zeitkomplexität der Algorithmen wird nach der Maximalzahl der eingesetzten Hilfsprogramme beurteilt. Die vorgestellten Algorithmen lassen sich modifizieren zur Approximation der Projektion eines Polytops \({\mathcal P}\) auf einen affinen Teilraum des \(\mathbb{R}^d\), der von den ersten \(k\) \((k< d)\) Basisvektoren aufgespannt wird.
Mathematics Subject Classification ID: 65D18
Mathematics Subject Classification ID: 52B11
Mathematics Subject Classification ID: 65Y20
zbMATH DE Number: 2056262
zbMATH Keywords: Boxes
zbMATH Keywords: Containment
zbMATH Keywords: Reachability analysis
zbMATH Keywords: algorithms
zbMATH Keywords: complexity
reviewed by: Oswald Giering
describes a project that uses: cdd
MaRDI profile type: Publication
cites work: Computing the volume is difficult
cites work: Convexity recognition of the union of polyhedra
cites work: Q4518985
cites work: Two Algorithms for Determining Volumes of Convex Polyhedra
cites work: Optimal scaling of balls and polyhedra
cites work: On the complexity of four polyhedral set containment problems
cites work: Q4348479
cites work: Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces
cites work: On the complexity of some basic problems in computational convexity. I. Containment problems
cites work: Q4324980
cites work: Q4936005
cites work: Lectures on Polytopes
description: scientific article; zbMATH DE number 2056262