| Ham-Sandwich Cuts and Other Tasks in Arrangements (2007) | |||||||||||||||
Abstract | |||||||||||||||
| Given a set L = {ℓ1,...,ℓn} of n lines in general position in the plane and subsets A and B of vertices in the arrangement A(L), the goal is to find a line that simultaneously bisects both A and B. We give an O(n(logn) 2) algorithm for this task, in the special case where A and B are the vertices in different halfspaces, and an O(n(logn) 3) algorithm for non-separated cases. These statements should be compared to an Ω(n logn) lower bound, and to the O(n 2) complexity of the known ham-sandwich algorithm that is optimal for arbitrary sets of size O(n 2) but which does not exploit the fact that the points are vertices in a line arrangement. Several new algorithmic techniques for arrangements are also presented. They were needed for the ham sandwich results and are of independent interest. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||