Английская Википедия:Convex cap
A convex cap, also known as a convex floating body[1] or just floating body,[2] is a well defined structure in mathematics commonly used in convex analysis for approximating convex shapes. In general it can be thought of as the intersection of a convex Polytope with a half-space.
Definition
A cap, <math>C</math> can be defined as the intersection of a half-space <math>H</math> with a convex set <math>K</math>. Note that the cap can be defined in any dimensional space. Given a <math>\lambda \geq 1</math>, <math>C^\lambda</math> can be defined as the cap containing <math>C</math> corresponding to a half-space parallel to <math>H</math> with width <math>\lambda</math> times greater than that of the original.
The definition of a cap can also be extended to define a cap of a point <math>x</math> where the cap <math>C</math> can be defined as the intersection of a convex set <math>K</math> with a half-space <math>H</math> containing <math>x</math>. The minimal cap of a point is a cap of <math>x</math> with <math>\operatorname{vol}(C(x)) = \operatorname{min}\{\operatorname{vol}(K \cap H) : x \in H\}</math>.[3][4]
Floating Bodies and Caps
We can define the floating body of a convex shape <math>H</math> using the following process. Note the floating body is also convex. In the case of a 2-dimensional convex compact shape <math>K</math>, given some <math>\delta > 0</math> where <math>\delta</math> is small. The floating body of this 2-dimensional shape is given by removing all the 2 dimensional caps of area <math>\delta</math> from the original body. The resulting shape will be our convex floating body <math>K\delta</math>. We generalize this definition to n dimensions by starting with an n dimensional convex shape and removing caps in the corresponding dimension.
Relation to affine surface area
As <math>\delta \rightarrow 0</math>, the floating body more closely approximates <math>K</math>. This information can tell us about the affine surface area <math>\Omega(K)</math> of <math>K</math> which measures how the boundary behaves in this situation. If we take the convex floating body of a shape, we notice that the distance from the boundary of the floating body to the boundary of the convex shape is related to the convex shape's curvature. Specifically, convex shapes with higher curvature have a higher distance between the two boundaries. Taking a look at the difference in the areas of the original body and the floating body as <math>\delta \rightarrow 0</math>. Using the relation between curvature and distance, we can deduce that <math>A(K) - A(K\delta)</math> is also dependent on the curvature. Thus,
- <math>\Omega(K) = \int_{\operatorname{bd} K} {\kappa(x)^{\frac{1}{3}}dl} \approx \frac{A(K) - A(K\delta)}{\delta^{\frac{2}{3}}}</math>.[5]
In this formula, <math>\kappa(x)</math> is the curvature of <math>\operatorname{bd} K</math> at <math>x</math> and <math>l</math> is the length of the curve.
We can generalize distance, area and volume for n dimensions using the Hausdorff measure. This definition, then works for all <math>n \geq 0</math>. As well, the power of <math>\kappa(x)</math> is related to the inverse of <math>n + 1</math> where <math>n</math> is the number of dimensions. So, the affine surface area for an n-dimensional convex shape is
- <math>\int_{\operatorname{bd} K} {\kappa(x)^{\frac{1}{n + 1}}d\sigma(x)} \approx \frac{A(K) - A(K\delta)}{\delta^{\frac{2}{n + 1}}}</math>
where <math>\sigma(x)</math> is the <math>(n - 1)</math>-dimensional Hausdorff measure.[5]
Wet part of a convex body
The wet part of a convex body can be defined as <math>K(t) = K(v \leq t) = \{x \in K : v(x)\leq t \}</math> where <math>t</math> is any real number describing the maximum volume of the wet part and <math>v(x) = \operatorname{min}\{\operatorname{vol}(K \cap H): x \in H\}</math>.[3][4]
We can see that using a non-degenerate linear transformation (one whose matrix is invertible) preserves any properties of <math>K(t)</math>. So, we can say that <math>v: K \rightarrow \mathbb{R}</math> is equivariant under these types of transformations. Using this notation, <math>v_{AK}(Ax) = |\mathrm{det} A|v_K(x)</math>. Note that
- <math>\frac{\mathrm{vol}(K(v \leq t\mathrm{vol}(K)))}{\mathrm{vol}(K)}</math>
is also equivariant under non-degenerate linear transformations.
Caps for approximation
Assume <math>K \in \mathcal{K_1} = \{K: \mathrm{vol}(K) = 1\}</math> and choose <math>x_1, ... , x_n</math> randomly, independently and according to the uniform distribution from <math>K</math>. Then, <math>K_n = \text{conv}\{x_1, ..., x_n\}</math> is a random polytope.[3] Intuitively, it is clear that as <math>n \rightarrow \infty</math>, <math>K_n</math> approaches <math>K</math>. We can determine how well <math>K_n</math> approximates <math>K</math> in various measures of approximation, but we mainly focus on the volume. So, we define <math>E(K, n) = E(\mathrm{vol}K - \mathrm{vol}K_n)</math>, when <math>E</math> refers to the expected value. We use <math>K(t) = K(v \leq t)</math> as the wet part of <math>K</math> and <math>K(v \geq t)</math> as the floating body of <math>K</math>. The following theorem states that the general principle governing <math>E(K, n)</math> is of the same order as the magnitude of the volume of the wet part with <math>t = \frac{1}{n}</math>.
Theorem
For <math>K \in \mathcal{K}_1</math> and <math>n \geq d + 1</math>, <math>\mathrm{vol}K(\frac{1}{n}) \ll E(K, n) \ll \mathrm{vol}K(\frac{1}{n})</math>.[3] The proof of this theorem is based on the technique of M-regions and cap coverings. We can use the minimal cap which is a cap <math>C(x)</math> containing <math>x</math> and satisfying <math>\mathrm{vol}C(x) = v(x)</math>. Although the minimal cap is not unique, this doesn't have an effect on the proof of the theorem.
Lemma
If <math>x \in K</math> and <math>v(x) < \varepsilon_0</math>, then <math>C(x) \subset M(x, 3d)</math> for every minimal cap <math>C(x)</math>.[3]
Since <math>M(x) \subset C^2(x)</math>, this lemma establishes the equivalence of the M-regions <math>M(x)</math> and a minimal cap <math>C(x)</math>: a blown up copy of <math>M(x)</math> contains <math>C(x)</math> and a blown up copy of <math>C(x)</math> contains <math>M(x)</math>. Thus, M-regions and minimal caps can be interchanged freely, without losing more than a constant factor in estimates.
Economic cap covering
A cap covering can be defined as the set of caps that completely cover some boundary <math>D</math>. By minimizing the size of each cap, we can minimize the size of the set of caps and create a new set. This set of caps with minimal volume is called an economic cap covering and can be explicitly defined as the set of caps <math>C</math> covering some boundary <math>D</math> where each <math>C_i</math> has some minimal width <math>\varepsilon</math> and the total volume of this covering is ≪ <math>\varepsilon</math> ⋅ <math>vol(D)</math>.[3]
References
