Guarding Scenes against Invasive Hypercubes.
Mark de Berg, Haggai David, Matthew J. Katz, Mark H. Overmars, A. Frank van der Stappen, Jules Vleugels · 1998
A set of points G is a -guarding set for a set of objects O, if any hypercube not containing a point from G in its interior intersects at most objects of O. This definition underlies a new input model, that is both more general than de Berg's unclutteredness, and retains its main property: a d-dimensional scene satisfying the new model's requirements is known to have a linear-size binary space partition. We propose several algorithms for computing -guarding sets, and evaluate them experimentally. One of them appears to be quite practical.