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+ɛ)c (S), for 0 < ɛ ≤ 1 , in [`(O)]\bar O ((log |S|)/ɛ) 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.
Keywords Geometric optimization, Piercing set, Dynamic algorithms.