## Abstract

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 language | British English |
---|---|

State | Published - 2011 |

Event | 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011 - Toronto, ON, Canada Duration: 10 Aug 2011 → 12 Aug 2011 |

### Conference

Conference | 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011 |
---|---|

Country/Territory | Canada |

City | Toronto, ON |

Period | 10/08/11 → 12/08/11 |