Name
Abstract | ||
|---|---|---|
We consider the problems of computing maximal points and the convex hull of a set of points in two dimensions, when the points are “in motion.” We assume that the point locations (or trajectories) are not known precisely and determining these values exactly is feasible, but expensive. In our model the algorithm only knows areas within which each of the input points lie, and is required to identify the maximal points or points on the convex hull correctly by updating some points (i.e., determining their location exactly). We compare the number of points updated by the algorithm on a given instance to the minimum number of points that must be updated by a nondeterministic strategy in order to compute the answer provably correctly. We give algorithms for both of the above problems that always update at most three times as many points as the nondeterministic strategy, and show that this is the best possible. Our model is similar to that in [3] and [5]. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/3-540-44849-7_9 | Theory of Computing Systems / Mathematical Systems Theory |
Keywords | Field | DocType |
Computational Mathematic,Convex Hull,Point Location,Maximal Point,Input Point | Discrete mathematics,Combinatorics,Nondeterministic algorithm,Point location,Convex combination,Convex hull,Geometric computing,Mathematics | Journal |
Volume | Issue | ISSN |
38 | 4 | 0302-9743 |
ISBN | Citations | PageRank |
3-540-40176-8 | 12 | 0.66 |
References | Authors | |
8 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Richard Bruce | 1 | 261 | 129.90 |
| Michael Hoffmann | 2 | 12 | 0.66 |
| Danny Krizanc | 3 | 1778 | 191.04 |
| Rajeev Raman | 4 | 1550 | 110.81 |