VVZ API is not affiliated with ETH Zurich. Data might be outdated or incorrect. Please view the official ETHZ Vorlesungsverzeichnis for binding information.
Approximate Methods in Geometry
Last Updated: 2026-02-05 15:29:33
Abstract
The course is concerned with approximate geometric methods for the analysis of large data sets represented by point clouds. Concrete topics areLow Distortion Embedding, Approximate Nearest Neighbor Search, Semi Definite Programming, Approximations and Nets, Approximate Smallest Enclosing Balls and Boxes, Directional Width, Support Vector Machines.
Content
The course is concerned with approximate geometric methods for the analysis of large data sets represented by point clouds. Data is being collected in order to draw conclusions from it, i.e. to discover relations, make extrapolations into the future, etc. More often than not, data comes as a set or sequence of points describing objects, with each coordinate representing some quantification of some feature. On a computer such data is just a sequence of 0's and 1's; the need to analyze and "understand" it calls for means to support the process. One way is to visualize the data. For example, a data set representing a number of people by their respective heights and weights can be drawn as a point set in the plane, and this drawing may reveal some correlation that could be approximated by a linear function. For a wide range of applications (brain research, robotics, statistics, bioinformatics, character and speech recognition, computer graphics etc.) this approach is too simplistic, for various reasons. First of all, the size of the data may be huge (in the millions and billions, and sometimes so huge that we cannot even store it). And secondly, objects may have many features, giving rise to sets of dimension in the hundreds - and we know that simple visualization methods tend to fail starting in dimension 4. (Many features may in fact be redundant, but it is part of the endeavour to find out which ones.) Many of the arising problems appear to be too hard to be solved exactly in an efficient fashion. The course discusses several approximate methods for the analysis of large high-dimensional data sets that have been developed over the last years in response to the issues indicated above. While we have applications in mind for the questions we address, we emphasize theoretical aspects in the solutions (in particular, methods with guaranteed performance bounds). Methods we cover are random sampling, grid structures, core-sets, well separated pair decomposition, low distortion low-dimensional embeddings. Problems we address are shape and dimension analysis, nearest neighbor search, clustering etc. Examples for specific questions arising in these applications are the following: For some point in d-space, what is its closest neighbor in the point cloud? What is the closest pair in the point cloud? What is the "best" grouping of the points in the cloud into k groups? Which subset of the point set of size k provides the "best" description of the point cloud? What is the dimensionality of the point cloud and what does dimensionality mean here? Can the point cloud be embedded into a lower-dimensional space while preserving many of its characteristics?
General Information
- Language
- English
- Levels
- BSC , DS , MSC
- Frequency
- Yearly recurring
Examination
- Type
- session examination
- Mode
- oral 15 minutes
Course Components
| Type | Title | Time & Place | Hours |
|---|---|---|---|
| lecture | Approximate Methods in Geometry |
|
2 h weekly |
| exercise | Approximate Methods in Geometry |
|
1 h weekly |