Loading...
Please wait, while we are loading the content...
Similar Documents
Facility Location on Terrains (Extended Abstract)
| Content Provider | Semantic Scholar |
|---|---|
| Author | Aronov, Boris Kreveld, Marc J. Van Oostrum, Ronald William Van Varadarajan, Kasturirangan |
| Copyright Year | 1998 |
| Abstract | Given a terrain defined as a piecewise-linear function with n triangles, and m point sites on it, we would like to identify the location on the terrain that minimizes the maximum distance to the sites. The distance is measured as the length of the Euclidean shortest path along the terrain. To simplify the problem somewhat, we extend the terrain to (the surface of) a polyhedron. To compute the optimum placement, we compute the furthest-site Voronoi diagram of the sites on the polyhedron. The diagram has maximum combinatorial complexity Θ(mn 2 ), and the algorithm runs in O(mn 2 log 2 m(log m +l ogn)) time. |
| Starting Page | 19 |
| Ending Page | 28 |
| Page Count | 10 |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://page-one.springer.com/pdf/preview/10.1007/3-540-49381-6_4 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
