Output-Sensitive Algorithms for Enumerating Minimal Transversals for Some Geometric Hypergraphs.

We give a general framework for the problem of finding all minimal hitting sets of a family of objects in ]> by another. We apply this framework to the following problems: (i) hitting hyper-rectangles by points in ]> ; (ii) stabbing connected objects by axis-parallel hyperplanes in ]> ; and (iii) hitting half-planes by points. For both the covering and hitting set versions, we obtain incremental polynomial-time algorithms, provided that the dimension d is fixed. [ABSTRACT FROM AUTHOR]