direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

On Finding Points in General Position

Vincent Froese (TU Berlin)

We study computational aspects of the General Position Subset Selection problem, that is, given a set of n points in the plane and an integer k, find a subset of points in general position of size at least k. We prove several hardness results including NP- and APX-hardness, as well as an exponential running time lower bound based on the Exponential Time Hypothesis. On the positive side, we show that an existing O(k^4)-point problem kernel by Cao (2012) can be improved to O(k^3) points. We also show a problem kernel containing O(h^2) points for the dual parameter h := n - k and prove that this is essentially optimal by adapting a framework of Kratsch et al. (2014). We conclude with several open questions.

Vincent Froese
TEL 512

Back to the research colloquium site.

Zusatzinformationen / Extras