MYSTEVENS PEOPLE FINDER MAKE A GIFT

 ABOUT Mission   History   Visit Departments   Dean's Office Faculty & Staff
 UNDERGRADUATE Programs   Curriculum Design Spine   Advising Global Opportunities   Admissions
 GRADUATE Programs   Admissions
 RESEARCH Centers & Labs
 RESOURCES Students   Faculty   Industry   Alumni   Green@Stevens

 News Events Share Print

# News Highlight

 Back

 CS Department Seminar: Esther Ezra (New York University)September 24, 2012 Title: On the Geometric Hitting-Set Problem. Speaker: Esther Ezra, New York University Time: 2:00pm-3:30pm Location: Babbio Center 110 Abstract: Given a set X of elements and a set R consisting of subsets of X (also called "ranges"), the hitting-set problem is to find a smallest subset of X with the property that each range in R contains an element of X. In a typical geometric scenario, the elements of X are points in d-space and the elements of R are simply-shaped regions in that space, e.g., X can be a set of points in the plane and R can represent a set of unit-disks. This problem is not only greatly fundamental and has been well-studied, butalso has various applications to sensor networking, art-gallery and facility location problems. A related (dual) problem is the set-cover problem, where the goal is to find a smallest subcollection of R, whose union covers X. While the general (non-geometric) primal and dual problems are NP-Hard to solve, and hard to approximate up to a logarithmic factor, there exist polynomial-time approximation algorithms that yield smaller approximation factors in various geometric settings. This improvement is achieved due to the existence of small size Epsilon-nets in geometric settings. In the primal problem, an Epsilon-net is a subset of the elements in X that hit all the "heavy" regions (that is, regions that contain at least anEpsilon-fraction of the elements in X), and in the dual problem, an Epsilon-net is a subset of the regions in R that cover all the "deep" points (that is, points that are contained in at least an Epsilon-fraction of the regions). In other words, in the primal setting an Epsilon-net is a hitting set for all the heavy regions, and in the dual setting an Epsilon-net is a set-cover for all the deep points. In this talk I will discuss various improved bounds on the size of Epsilon-nets for both primal and dual settings. In particular, I will emphasize the connection between combinatorial bounds on the complexity of the union of simply-shaped regions and bounds on the size of Epsilon-nets, and show how tightening the first improves the latter. Joint Work with Boris Aronov (Polytechnic Institute of NYU), and Micha Sharir (Tel Aviv University). Bio: I am a visiting professor at Department of Computer Science at Courant Institute of Mathematical Sciences, New York University. I obtained my Ph.D degree from Department of Computer Science, Tel-Aviv University in 2007. I did my Postdoctoral research  at Department of Computer Science, Duke University in the years 2007--2009, and in  Courant Institute of Mathematical Sciences in the years 2009-2011. I received NSF Fellowship in 2012.For more information please contact: Wendy WangAssistant Professor Babbio 620Phone: 201.216.8736hwang4@stevens.eduThe Innovation University TM

 News & Events Archive

News Archive

Events Archive

Newsletter Archive

 Contact

The Office of Academic Communications and Assessment collaborates with faculty, students and administration to provide a variety of online tools and services including web development, multimedia assets and course surveys:

Christine del Rosario
Director of Academic Communications & Assessment
Edwin A. Stevens Hall
Room 406
Phone: 201.216.5561
Fax: 201.216.8090
Email: cdelrosa@stevens.edu