Skip to main content

approximation Approximation of convex body by polytopes

In a recent survey paper, http://link.springer.com/article/10.1007/s10958-008-9144-xApproximation of convex sets by polytopes, Bronstein claims that under Hausdorff distance $\rho_H$, for every convex body $U$, $$\rho_H(U,\mathcal{P}_n)\leq c(U) n^{-2/(d-1)},$$ where $\mathcal{P}_n$ is the set of all polytopes with at most $n$ vertices. It is claimed in the survey paper (pp.729, section 4.1) that the same estimate is also valid if we replace $\mathcal{P}_n$ with other sets, including (1) $\mathcal{I}_n(U)$, the set of all inscribed polytopes in $U$ with at most $n$ vertices; (2) $\mathcal{I}_{(n)}(U)$, the set of all inscribed polytopes in $U$ with at most $n$ facets; (3)$\mathcal{O}_n(U)$, the set of all polytopes circumscribing $U$ with at most $n$ vertices, and (4) $\mathcal{O}_{(n)}(U)$, the set of all polytopes circumscribing $U$ with at most $n$ facets.

My questions are:

(1) Is there any result concerning the symmetric difference metric with the same estimate? In particular I am interested in the case $\mathcal{O}_{(n)}(U)$. An upper bound would be fine. Preferably with explicit constants such as $c_1\cdot c_2(d)c_3(U)$ with $c_2,c_3$ explicitly defined. No smoothness of the boundary is assumed and I am currently not interested too much about the asymptotic expansion the error estimate (usually involving the Gaussian curvature somewhere)

(2) Similarly, do we have results that give an estimate of how well can polyhedral functions can approximate (good) convex function on a fixed domain $\Omega$?

approximation of convex body by polytopes

In a recent survey paper http://link.springer.com/article/10.1007/s10958-008-9144-x, Bronstein claims that under Hausdorff distance $\rho_H$, for every convex body $U$, $$\rho_H(U,\mathcal{P}_n)\leq c(U) n^{-2/(d-1)},$$ where $\mathcal{P}_n$ is the set of all polytopes with at most $n$ vertices. It is claimed in the survey paper (pp.729, section 4.1) that the same estimate is also valid if we replace $\mathcal{P}_n$ with other sets, including (1) $\mathcal{I}_n(U)$, the set of all inscribed polytopes in $U$ with at most $n$ vertices; (2) $\mathcal{I}_{(n)}(U)$, the set of all inscribed polytopes in $U$ with at most $n$ facets; (3)$\mathcal{O}_n(U)$, the set of all polytopes circumscribing $U$ with at most $n$ vertices, and (4) $\mathcal{O}_{(n)}(U)$, the set of all polytopes circumscribing $U$ with at most $n$ facets.

My questions are:

(1) Is there any result concerning the symmetric difference metric with the same estimate? In particular I am interested in the case $\mathcal{O}_{(n)}(U)$. An upper bound would be fine. Preferably with explicit constants such as $c_1\cdot c_2(d)c_3(U)$ with $c_2,c_3$ explicitly defined. No smoothness of the boundary is assumed and I am currently not interested too much about the asymptotic expansion the error estimate (usually involving the Gaussian curvature somewhere)

(2) Similarly, do we have results that give an estimate of how well can polyhedral functions can approximate (good) convex function on a fixed domain $\Omega$?

Approximation of convex body by polytopes

In a recent survey paper, Approximation of convex sets by polytopes, Bronstein claims that under Hausdorff distance $\rho_H$, for every convex body $U$, $$\rho_H(U,\mathcal{P}_n)\leq c(U) n^{-2/(d-1)},$$ where $\mathcal{P}_n$ is the set of all polytopes with at most $n$ vertices. It is claimed in the survey paper (pp.729, section 4.1) that the same estimate is also valid if we replace $\mathcal{P}_n$ with other sets, including (1) $\mathcal{I}_n(U)$, the set of all inscribed polytopes in $U$ with at most $n$ vertices; (2) $\mathcal{I}_{(n)}(U)$, the set of all inscribed polytopes in $U$ with at most $n$ facets; (3)$\mathcal{O}_n(U)$, the set of all polytopes circumscribing $U$ with at most $n$ vertices, and (4) $\mathcal{O}_{(n)}(U)$, the set of all polytopes circumscribing $U$ with at most $n$ facets.

My questions are:

(1) Is there any result concerning the symmetric difference metric with the same estimate? In particular I am interested in the case $\mathcal{O}_{(n)}(U)$. An upper bound would be fine. Preferably with explicit constants such as $c_1\cdot c_2(d)c_3(U)$ with $c_2,c_3$ explicitly defined. No smoothness of the boundary is assumed and I am currently not interested too much about the asymptotic expansion the error estimate (usually involving the Gaussian curvature somewhere)

(2) Similarly, do we have results that give an estimate of how well can polyhedral functions can approximate (good) convex function on a fixed domain $\Omega$?

added 5 characters in body
Source Link
Roy Han
  • 599
  • 3
  • 11

In a recent survey paper http://link.springer.com/article/10.1007%2FBF00967115http://link.springer.com/article/10.1007/s10958-008-9144-x, Bronstein claims that under Hausdorff distance $\rho_H$, for every convex body $U$, $$\rho_H(U,\mathcal{P}_n)\leq c(U) n^{-2/(d-1)},$$ where $\mathcal{P}_n$ is the set of all polytopes with at most $n$ vertices. It is claimed in the survey paper (pp.729, section 4.1) that the same estimate is also valid if we replace $\mathcal{P}_n$ with other sets, including (1) $\mathcal{I}_n(U)$, the set of all inscribed polytopes in $U$ with at most $n$ vertices; (2) $\mathcal{I}_{(n)}(U)$, the set of all inscribed polytopes in $U$ with at most $n$ facets; (3)$\mathcal{O}_n(U)$, the set of all polytopes circumscribing $U$ with at most $n$ vertices, and (4) $\mathcal{O}_{(n)}(U)$, the set of all polytopes circumscribing $U$ with at most $n$ facets.

My questions are:

(1) Is there any result concerning the symmetric difference metric with the same estimate? In particular I am interested in the case $\mathcal{O}_{(n)}(U)$. An upper bound would be fine. Preferably with explicit constants such as $c_1\cdot c_2(d)c_3(U)$ with $c_2,c_3$ explicitly defined. No smoothness of the boundary is assumed and I am currently not interested too much about the asymptotic expansion the error estimate (usually involving the Gaussian curvature somewhere)

(2) Similarly, do we have results that give an estimate of how well can polyhedral functions can approximate (good) convex function on a fixed domain $\Omega$?

In a recent survey paper http://link.springer.com/article/10.1007%2FBF00967115, Bronstein claims that under Hausdorff distance $\rho_H$, for every convex body $U$, $$\rho_H(U,\mathcal{P}_n)\leq c(U) n^{-2/(d-1)},$$ where $\mathcal{P}_n$ is the set of all polytopes with at most $n$ vertices. It is claimed in the survey paper (pp.729, section 4.1) that the same estimate is also valid if we replace $\mathcal{P}_n$ with other sets, including (1) $\mathcal{I}_n(U)$, the set of all inscribed polytopes in $U$ with at most $n$ vertices; (2) $\mathcal{I}_{(n)}(U)$, the set of all inscribed polytopes in $U$ with at most $n$ facets; (3)$\mathcal{O}_n(U)$, the set of all polytopes circumscribing $U$ with at most $n$ vertices, and (4) $\mathcal{O}_{(n)}(U)$, the set of all polytopes circumscribing $U$ with at most $n$ facets.

My questions are:

(1) Is there any result concerning the symmetric difference metric with the same estimate? In particular I am interested in the case $\mathcal{O}_{(n)}(U)$. An upper bound would be fine. No smoothness of the boundary is assumed and I am currently not interested too much about the asymptotic expansion the error estimate (usually involving the Gaussian curvature somewhere)

(2) Similarly, do we have results that give an estimate of how well can polyhedral functions can approximate (good) convex function on a fixed domain $\Omega$?

In a recent survey paper http://link.springer.com/article/10.1007/s10958-008-9144-x, Bronstein claims that under Hausdorff distance $\rho_H$, for every convex body $U$, $$\rho_H(U,\mathcal{P}_n)\leq c(U) n^{-2/(d-1)},$$ where $\mathcal{P}_n$ is the set of all polytopes with at most $n$ vertices. It is claimed in the survey paper (pp.729, section 4.1) that the same estimate is also valid if we replace $\mathcal{P}_n$ with other sets, including (1) $\mathcal{I}_n(U)$, the set of all inscribed polytopes in $U$ with at most $n$ vertices; (2) $\mathcal{I}_{(n)}(U)$, the set of all inscribed polytopes in $U$ with at most $n$ facets; (3)$\mathcal{O}_n(U)$, the set of all polytopes circumscribing $U$ with at most $n$ vertices, and (4) $\mathcal{O}_{(n)}(U)$, the set of all polytopes circumscribing $U$ with at most $n$ facets.

My questions are:

(1) Is there any result concerning the symmetric difference metric with the same estimate? In particular I am interested in the case $\mathcal{O}_{(n)}(U)$. An upper bound would be fine. Preferably with explicit constants such as $c_1\cdot c_2(d)c_3(U)$ with $c_2,c_3$ explicitly defined. No smoothness of the boundary is assumed and I am currently not interested too much about the asymptotic expansion the error estimate (usually involving the Gaussian curvature somewhere)

(2) Similarly, do we have results that give an estimate of how well can polyhedral functions can approximate (good) convex function on a fixed domain $\Omega$?

Source Link
Roy Han
  • 599
  • 3
  • 11

approximation of convex body by polytopes

In a recent survey paper http://link.springer.com/article/10.1007%2FBF00967115, Bronstein claims that under Hausdorff distance $\rho_H$, for every convex body $U$, $$\rho_H(U,\mathcal{P}_n)\leq c(U) n^{-2/(d-1)},$$ where $\mathcal{P}_n$ is the set of all polytopes with at most $n$ vertices. It is claimed in the survey paper (pp.729, section 4.1) that the same estimate is also valid if we replace $\mathcal{P}_n$ with other sets, including (1) $\mathcal{I}_n(U)$, the set of all inscribed polytopes in $U$ with at most $n$ vertices; (2) $\mathcal{I}_{(n)}(U)$, the set of all inscribed polytopes in $U$ with at most $n$ facets; (3)$\mathcal{O}_n(U)$, the set of all polytopes circumscribing $U$ with at most $n$ vertices, and (4) $\mathcal{O}_{(n)}(U)$, the set of all polytopes circumscribing $U$ with at most $n$ facets.

My questions are:

(1) Is there any result concerning the symmetric difference metric with the same estimate? In particular I am interested in the case $\mathcal{O}_{(n)}(U)$. An upper bound would be fine. No smoothness of the boundary is assumed and I am currently not interested too much about the asymptotic expansion the error estimate (usually involving the Gaussian curvature somewhere)

(2) Similarly, do we have results that give an estimate of how well can polyhedral functions can approximate (good) convex function on a fixed domain $\Omega$?