Computing hitting sets for half-planes
This interesting paper deals with computing sets for half planes. To gain some perspective on the problem studied, we need to start with some definitions. Thus let \(P\) be a set of points in the plane and also let \(H\) be a set of half planes in the plane. The points and planes are scaled (weighted) to have number \(n\). Then a point hits a half plane if the half plane contains the point. With this in mind, a subset of \(P\) say \(P'\) is a hitting set for \(H\) if every half-plane in \(H\) is hit by a point in \(P'\). Consequently, \(P'\) is a minimum-weight hitting set if the total weight of all points of \(P'\) is the smallest among all hitting sets of half planes \(H\). The purpose of the paper under consideration is to study the ``half plane hitting set problem which sets out to compute a minimum-weight hitting for \(H\). For a detailed survery of constributions to this problem, we refer the reader to the paper under review. In this paper, the authors construct an algorithm with runtime \(O(n^{5/2}\log^{2}n)\) improving on previous results. More specifically, their algorithm runs in \(O(\alpha n^{3/2}\log^{2}n)\) time where \(\alpha\) is the minimum number of points of \(P\) covered by any half-plane of \(H\). For the unweighted case where all points have the same weight, their algorithm runs in \(O(n\log n)\) time improving on earler results.\N\NThe paper is well written with a good set of references.
This page was built for publication: Computing hitting sets for half-planes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7230781)
