Inner and outer approximations of polytopes using boxes. (Q1428115): Difference between revisions

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.