Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, April 25, 2017, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Manuel Wettstein
Let P be a set of n points in the plane. The order type \chi of P is a function which assigns an orientation (clockwise or counterclockwise) to every ordered triple in P. The radial system R of P describes the (counterclockwise) radial order in which all other points are encountered around each point in P. While given \chi it is easy to construct the corresponding R, the converse is not true and there might be more than one solution. We give an algorithm that takes R as input and, after O(n) time of preprocessing, allows constant-time queries to all order types that are consistent with R.
Joint work with Oswin Aichholzer, Vincent Kusters, Wolfgang Mulzer, and Alexander Pilz.
Automatic MiSe System Software Version 1.4803M | admin login