Maintenance of a Piercing Set for Intervals with Applications

We show how to efficiently maintain a minimum piercing setfor a set $ of intervals on the line, under insertions and deletions to/from$. A linear-size dynamic data structure is presented, which enables usto compute a new minimum piercing set following an insertion or deletionin time 0(c($) log [$D, where c($) is the size of the new minimumpiercing set. We also show how to maintain a piercing set for $ of size atmost (1 +e)c(3), for 0 e _ 1, in 0(1) amortized time per update.