Loading...
Please wait, while we are loading the content...
Similar Documents
Kinetic Convex Hulls in the Black-Box Model
| Content Provider | Semantic Scholar |
|---|---|
| Author | Berg, D. Roeloffzen, Mjm Marcel Speckmann, Bettina |
| Copyright Year | 2011 |
| Abstract | Over the past decade, the kinetic-data-structures framework has become the standard in computational geometry for dealing with moving objects. A fundamental assumption underlying the framework is that the motions of the objects are known in advance. This assumption severely limits the applicability of KDSs. We study KDSs in the black-box model, which is a hybrid of the KDS model and the traditional timeslicing approach. In this more practical model we receive the position of each object at regular time steps and we have an upper bound on dmax, the maximum displacement of any point in one time step. We study the maintenance of the convex hull of a planar point set P in the black-box model, under the following assumption on dmax: there is some constant k such that for any pointp2 P the disk of radiusdmax contains at most k points. We analyze our algorithms in terms of k, the so-called k-spread of P . We show how to update the convex hull at each time step in O(k k log 2 n) amortized time. |
| Starting Page | 201 |
| Ending Page | 204 |
| Page Count | 4 |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://pure.tue.nl/ws/files/107881978/Metis253584.pdf |
| Alternate Webpage(s) | http://alexandria.tue.nl/openaccess/Metis253584.pdf |
| Alternate Webpage(s) | https://pure.tue.nl/ws/files/3718769/Metis253584.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
