Enumerating minimal transversals of geometric hypergraphs

Khaled Elbassioni, Imran Rauf, Saurabh Ray

Research output: Contribution to conferencePaperpeer-review

2 Scopus citations


We consider the problem of enumerating all minimal hitting sets of a given hypergraph (V,R), where V is a finite set, called the vertex set and R is a set of subsets of V called the hyperedges. We show that, when the hypergraph admits a balanced subdivision, then a recursive decomposition can be used to obtain efficiently all minimal hitting sets of the hypergraph. We apply this decomposition framework to get incremental polynomial-time algorithms for finding minimal hitting sets and minimal set covers for a number of hypergraphs induced by a set of points and a set of geometric objects. The set of geometric objects includes half-spaces, hyper-rectangles and balls, in fixed dimension. A distinguishing feature of the algorithms we obtain is that they admit an effi- cient global parallel implementation, in the sense that all minimal hitting sets can be generated in polylogarith- mic time in V , R and the total number of minimal transversals T, using a polynomial number of processors.

Original languageBritish English
StatePublished - 2011
Event23rd Annual Canadian Conference on Computational Geometry, CCCG 2011 - Toronto, ON, Canada
Duration: 10 Aug 201112 Aug 2011


Conference23rd Annual Canadian Conference on Computational Geometry, CCCG 2011
CityToronto, ON


Dive into the research topics of 'Enumerating minimal transversals of geometric hypergraphs'. Together they form a unique fingerprint.

Cite this