Journal
DISCRETE & COMPUTATIONAL GEOMETRY
Volume 51, Issue 2, Pages 438-461Publisher
SPRINGER
DOI: 10.1007/s00454-013-9561-6
Keywords
Embedding; Dimension reduction; Hyperplane tessellations; Mean width; Near isometry
Categories
Funding
- NSF Postdoctoral Research Fellowship [1103909]
- NSF [DMS 0918623, 1001829]
- Direct For Mathematical & Physical Scien [1001829] Funding Source: National Science Foundation
- Division Of Mathematical Sciences [1001829] Funding Source: National Science Foundation
- Division Of Mathematical Sciences
- Direct For Mathematical & Physical Scien [1103909] Funding Source: National Science Foundation
Ask authors/readers for more resources
Given a subset K of the unit Euclidean sphere, we estimate the minimal number m=m(K) of hyperplanes that generate a uniform tessellation of K, in the sense that the fraction of the hyperplanes separating any pair x,yaK is nearly proportional to the Euclidean distance between x and y. Random hyperplanes prove to be almost ideal for this problem; they achieve the almost optimal bound m=O(w(K)(2)) where w(K) is the Gaussian mean width of K. Using the map that sends xaK to the sign vector with respect to the hyperplanes, we conclude that every bounded subset K of embeds into the Hamming cube {-1,1} (m) with a small distortion in the Gromov-Haussdorff metric. Since for many sets K one has m=m(K)a parts per thousand(a)n, this yields a new discrete mechanism of dimension reduction for sets in Euclidean spaces.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available