Name
Abstract | ||
|---|---|---|
In recent years realistic input models for geometric algorithms have been studied. The most important models introduced are fatness, low density, unclutteredness and small simple-cover complexity. These models form a strict hierarchy. Unfortunately, small simple-cover complexity is often too general to enable efficient algorithms. In this paper we introduce a new model based on guarding sets. Informally, a guarding set for a collection of objects is a set of points that approximates the distribution of the objects. Any axis-parallel hyper-cube that contains no guards in its interior may intersect at most a constant number of objects. We show that guardable scenes fit in between unclutteredness and small simple-cover complexity. They do enable efficient algorithms, for example a linear size binary space partition. We study properties of guardable scenes and give heuristic algorithms to compute small guarding sets. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1016/S0925-7721(03)00016-6 | Computational Geometry: Theory and Applications |
Keywords | DocType | Volume |
constant number,geometric algorithm,low density,invasive hypercubes,small simple-cover complexity,important model,efficient algorithm,input models,guarding sets,guarding scene,heuristic algorithm,guardable scene,epsilon-nets,axis-parallel hyper-cube,linear size binary space | Conference | 26 |
Issue | ISSN | Citations |
2 | Computational Geometry: Theory and Applications | 11 |
PageRank | References | Authors |
0.59 | 11 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mark De Berg | 1 | 1497 | 153.24 |
| Haggai David | 2 | 17 | 1.51 |
| Matthew J. Katz | 3 | 225 | 19.92 |
| Mark H. Overmars | 4 | 4572 | 518.80 |
| A. Frank Van Der Stappen | 5 | 1069 | 84.44 |
| Jules Vleugels | 6 | 297 | 21.80 |