offered by Herman Haverkort

Kick-off meeting: to be scheduled. Please contact Herman Haverkort.

This seminar covers research papers in Computational Geometry. Together we will study papers related to a particular topic. For this semester, the topic is data structures for data in high-dimensional or non-Euclidean spaces. A typical query about such data asks to report all data points that lie within a certain query range, or the data points that lie closest to a given query point. It is relatively easy to design efficient data structures for such queries if data points are described by only two coordinates and distances are measured by taking the usual Euclidean distance between the corresponding points in the plane. But if the data is high-dimensional or distances are measured differently, the problem becomes more challenging. The plan is to study a selection of papers that tell us something about:

• lower bounds: how much space (or query time) do we need, in the worst case, as a function of the number of data points and the number of dimensions, if we require that our data structure conforms to a reasonable model of computation and guarantees a certain worst-case query time (or data structure size, respectively)?
• approximate solutions with provable guarantees on expected performance (accuracy, query time, data structure size), for example, locality-sensitive hashing, or solutions via dimension-reduction techniques;
• practical exact solutions, and the gap between performance in practice and theoretical worst-case performance.

The papers will be distributed over the students; each student will prepare a concise summary of the paper(s) assigned to them, present this in a Zoom meeting, and lead a critical discussion with other participants in the seminar. The planned workload is 120 hours (4 CP).

The exact format, scope and selection of papers will depend on the number of participants. If you are interested in participating, please contact Herman Haverkort as soon as possible.

The contents of the seminar will be related to the topics of the lectures Foundations of Computational Geometry and Discrete and Computational Geometry. If you have taken these classes, this will be helpful, but it is not necessary.