Maintenance of a Piercing Set for Intervals with Applications

Maintenance of a Piercing Set for Intervals with Applications

0.00 Avg rating0 Votes
Article ID: iaor20118107
Volume: 36
Issue: 1
Start Page Number: 59
End Page Number: 73
Publication Date: May 2003
Journal: Algorithmica
Authors: , ,
Keywords: optimization, sets
Abstract:

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 ¯ equ1 ((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.

Reviews

Required fields are marked *. Your email address will not be published.