Name
Abstract | ||
|---|---|---|
We present several efficient dynamic data structures for point-enclosure queries, involving convex fat objects in R 2 or R 3 . Our planar structures are actually fitted for a more general class of objects – (β,δ) -covered objects – which are not necessarily convex, see definition below. These structures are more efficient than alternative known structures, because they exploit the fatness of the objects. We then apply these structures to obtain efficient solutions to two problems: (i) finding a perfect containment matching between a set of points and a set of convex fat objects, and (ii) finding a piercing set for a collection of convex fat objects, whose size is optimal up to some constant factor. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1016/S0925-7721(99)00059-0 | Computational Geometry: Theory and Applications |
Keywords | DocType | Volume |
fat object,dynamic data structure,piercing set,containment matching,dynamic data structures,point enclosure,fat objects | Conference | 15 |
Issue | ISSN | ISBN |
4 | 0925-7721 | 3-540-63307-3 |
Citations | PageRank | References |
27 | 1.61 | 25 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alon Efrat | 1 | 1312 | 93.92 |
| Matthew J. Katz | 2 | 225 | 19.92 |
| Frank Nielsen | 3 | 1256 | 118.37 |
| Micha Sharir | 4 | 8405 | 1183.84 |
| MJ Katz | 5 | 58 | 4.10 |