Name
Abstract | ||
|---|---|---|
We study the problem of computing the set of all distant hori- zons of a terrain, represented as either: the set of all edges that appear in the set of all distant horizons; the connected sets in the union of all points that appear in the set of all dis- tant horizons (the set of edge fragments); or a search struc- ture to efciently calculate the edge fragments or edges on a distant horizon from a particular viewing direction. We describe a randomized algorithm that can be used to solve all three forms of the problem with an expected run time of O(n2+ ) for any > 0 where n is the number of edges in the piecewise linear terrain. We show that solving either of the rst two versions of the problem is 3SUM hard, and we also construct a terrain with a single local maxima and a quadratic number of edge fragments in the set of all distant horizons, showing that our solution to the second version of the prob- lem is essentially optimal. |
Year | Venue | Keywords |
|---|---|---|
2004 | CCCG | piecewise linear,randomized algorithm |
Field | DocType | Citations |
Discrete mathematics,Combinatorics,Computer science,Terrain | Conference | 2 |
PageRank | References | Authors |
0.38 | 13 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| William S. Evans | 1 | 543 | 60.69 |
| Daniel Archambault | 2 | 705 | 39.10 |
| David G. Kirkpatrick | 3 | 2394 | 541.05 |