Loading
Research Projects
Dynamic Algorithms for Geometric Hitting Set and Set Cover Problems
|
Abstract
Given a range space (X,R), where the universe X is a set of items and R is a collection of subsets of X, the hitting set problem asks for the smallest subset H of X such that H intersects every range in R. Similarly, the set cover problem is to find the smallest collection C of R such that the union of all ranges in C is X. In many geometric applications, X is a set of points in the d-dimensional Euclidean space and each range in R is the intersection of X and a geometric object in $R^d$ such as disk and square. It is known that the greedy algorithm achieves the optimal approximation ratio for both problems in general (Feige and Uriel, 1998). However, in the geometric setting, where R is induced by simple geometric shapes, better approximation algorithms have been shown to exist. While numerous studies have considered these problems for the static setting, little work has been done for the dynamic setting, where members of X and R are allowed be inserted and deleted over time. In this project, we aim to develop efficient dynamic algorithms for geometric hitting set and set cover problems. We consider cases where R consists of simple geometric objects such as intervals and squares.
Advisor(s): Pankaj Agarwal
Jun Yang, Kamesh Munagala