An Optimal Algorithm for Half-plane Hitting Set

作     者：Liu, Gang Wang, Haitao 

作者机构：Kahlert School of Computing University of Utah Salt Lake CityUT84112 United States 

出 版 物：《arXiv》 (arXiv)

年 卷 期：2025年

核心收录：

主　　题：Optimization algorithms 

摘      要：Given a set P of n points and a set H of n half-planes in the plane, we consider the problem of computing a smallest subset of points such that each half-plane contains at least one point of the subset. The previously best algorithm solves the problem in O(n3 log n) time. It is also known that Ω(n log n) is a lower bound for the problem under the algebraic decision tree model. In this paper, we present an O(n log n) time algorithm, which matches the lower bound and thus is optimal. Another virtue of the algorithm is that it is relatively simple. Copyright © 2025, The Authors. All rights reserved.