Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, January 19, 2006, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Mirco Fröhlicher
Given a set of n points in the plane, pick an arbitrary horizontal line segment and move it vertically until it hits one of the points. This paper describes a linear size data structure to answer such dragging queries in O(log n) time with O(n log n) preprocessing time.
 B. Chazelle, An Algorithm for Segment-Dragging and Its Implementation, Algorithmica 3(2), pp. 205-221, 1998.
Automatic MiSe System Software Version 1.4803M | admin login