Article ID: | iaor20118107 |
Volume: | 36 |
Issue: | 1 |
Start Page Number: | 59 |
End Page Number: | 73 |
Publication Date: | May 2003 |
Journal: | Algorithmica |
Authors: | Nielsen , Katz , Segal |
Keywords: | optimization, sets |
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