Maintenance of a piercing set for intervals with applications
We show how to maintain efficiently a minimum piercing set for a set S of intervals on the line, under insertions and deletions to/from S. A linear-size dynamic data structure is presented, which enables us to compute a new minimum piercing set following an insertion or deletion in time O(c(S) log \S\), where c(S) is the size of the new minimum piercing set. We also show how to maintain a piercing set for S of size at most (1 + epsilon)c(S), for 0 < epsilon less than or equal to 1, in (O) over bar((log\S\)/epsilon) amortized time per update. We then apply these results to obtain efficient solutions to the following three problems: (i) the shooter location problem, (ii) computing a minimum piercing set for arcs on a circle, and (iii) dynamically maintaining a box cover for a d-dimensional point set.
piercing set geometric optimization dynamic algorithms