Inner and outer approximations of polytopes using boxes. (Q1428115)

From MaRDI portal
Revision as of 03:19, 5 March 2024 by Import240304020342 (talk | contribs) (Set profile property.)
scientific article
Language Label Description Also known as
English
Inner and outer approximations of polytopes using boxes.
scientific article

    Statements

    Inner and outer approximations of polytopes using boxes. (English)
    0 references
    0 references
    0 references
    0 references
    14 March 2004
    0 references
    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.
    0 references
    Boxes
    0 references
    Containment
    0 references
    Reachability analysis
    0 references
    algorithms
    0 references
    complexity
    0 references

    Identifiers