[Mittagsseminar TI] FW: [i-prof] Einladung zur Bachelorverteidigung

[Wolfgang Mulzer <mulzer@inf.fu-berlin.de>]

Dear all,

this will be the Mittagsseminar on Tuesday.

The talk will be given in English.

Please note the room *SR 031, Arnimallee 7*.

Cheers 

Wolfgang 

-------- Ursprüngliche Nachricht --------

Von: Philipp Kulbatskiy <philik04@zedat.fu-berlin.de>

Datum: 04.05.26 09:35 (GMT+01:00)

An: i-profs@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de, i-studi@inf.fu-berlin.de, maria.koekenhoff@fu-berlin.de

Cc: mulzer@inf.fu-berlin.de

Betreff: [i-prof] Einladung zur Bachelorverteidigung

Sehr geehrte Damen und Herren,

hiermit lade ich Sie herzlich zu meiner Bachelorverteidigung ein.

Titel der Arbeit:
„An Analysis of the Optimal Hitting Set Algorithm“

Termin:
Dienstag, 12. Mai, 12:00 Uhr

Ort:
SR 031, Arnimallee 7

Betreuer:
Prof. Dr. Wolfgang Mulzer

Zweitgutachter:
Max Willert

Abstract:
This thesis analyzes an optimal algorithm for the half-plane hitting set
problem in the plane. Given a set P of points and a set H of half-planes,
the goal is to compute a smallest subset P ′ ⊆ P such that every
half-plane in H contains at least one point of P ′. This problem is a
fundamental geometric optimization task with links to coverage, duality,
and algorithm design.
Earlier work solved the general problem in O(n³ log n) time, while a lower
bound of Ω(n log n) was known [4]. The algorithm studied in this thesis
closes this gap by achieving O(n log n) time, which is asymptotically
optimal. The key contribution is a reduction of the geometric hitting-set
instance to a circular-point coverage problem, followed by a structural
improvement that replaces a quadratic-size arc set with a linear-size
representative subset Â; the sufficiency of this reduction is formalized
in Lemma 2.
The thesis first introduces the formal model, assumptions, and lower-bound
context, then explains prior approaches and why they are not optimal for
the general setting. It then presents the reduction, proves correctness
via central lemmas and a corollary, and derives both intermediate and
final time bounds. Special attention is given to design choices,
bottlenecks, and the role of envelope-based pruning and data-structural
acceleration in obtaining linear-size candidate families.
The result shows that the half-plane hitting set problem can be solved as
fast as comparison-based sorting in the algebraic decision-tree model.
Beyond proving optimal asymptotic complexity, the analyzed approach is
notable for conceptual clarity compared with earlier multi-instance
reductions. The thesis concludes with related problems (coverage and
weighted variants), limitations, and possible directions for future
research.

Ich würde mich sehr über Ihre Teilnahme freuen.

Mit freundlichen Grüßen
Philipp Kulbatskiy

_______________________________________________
Automatischer Mailverteiler an Gruppe 'ml-i-prof-mi'.
Hinweise dazu siehe Hilfeseite:
https://www.mi.fu-berlin.de/w/Tec/AnkuendigungsVerteiler