Polytope Approximation and the Mahler Volume (Preprint)

Abstract

The problem of approximating convex bodies by polytopes is an important and well studied problem. Given a convex body K in Rd, the objective is to minimize the number of vertices (alternatively, the number of facets) of an approximating polytope for a given Hausdorff error epsilon. Results to date have been of two types. The first type assumes that K is smooth, and bounds hold in the limit as epsilon tends to zero. The second type requires no such assumptions. The latter type includes the well known results of Dudley (1974) and Bronshteyn and Ivanov (1976), which show that in spaces of fixed dimension, O((diam(K)=epsilon)(d-1)/2) vertices (alt., facets) suffice. Our results are of this latter type.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2012
Accession Number
ADA555010

Entities

People

  • David M. Mount
  • Guilherme D. Da Fonseca
  • Sunil Arya

Organizations

  • Hong Kong University of Science and Technology

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Bodies
  • Boundaries
  • Cells
  • Computer Science
  • Computers
  • Convex Bodies
  • Convex Sets
  • Coordinate Systems
  • Diameters
  • Geometry
  • Hong Kong
  • Ovum
  • Standards
  • Theorems
  • Two Dimensional
  • Universities

Fields of Study

  • Mathematics

Readers

  • Approximation Theory.
  • Business Analytics
  • Graph Algorithms and Convex Optimization.

Technology Areas

  • Space