## 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 | English (US) |
---|---|

State | Published - 2011 |

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

### Other

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

Country/Territory | Canada |

City | Toronto, ON |

Period | 8/10/11 → 8/12/11 |

## ASJC Scopus subject areas

- Computational Mathematics
- Geometry and Topology