Campus Event Calendar
Event Entry
What and Who
A Solution to Excercise 8.13 (The Maximum-Level Vertex in an Arrangement of Lines)
Kurt Mehlhorn
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 3, AG 4, RG1, MMCI, AG 2, INET, AG 5, SWS
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 4 February 2020
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
Exercise 8,13 in de Berg, van Krefeld, Overmars and Schwarzkopf reads: Given a set of n lines in the plane, give an O(n log n) algorithm to compute the maximum level of any vertex in the arrangement of the lines.
The problem is easy if the lines are in general position (no three passing through the same point). For degenerate inputs the problem seems to be much harder.
We (Danny Halperin, Sariel Har-Pelel, KM, Eunjin Oh, Micha Sharir) have made a step forward. For mildly degenerate inputs (many lines crossing at a point, but no identical lines) we have an O(n log n) algorithm. For the completely general case, we can do tildeO(n^{4/3}), but are still missing the O(n log n).
Contact
Kurt Mehlhorn
--email hidden
passcode not visible
logged in users only
Kurt Mehlhorn, 01/22/2020 09:26 -- Created document.