Randomized external-memory algorithms for some geometric problems
| Author(s) : | U. Meyer K. Mehlhorn P. Ferragina A. Crauser E. Ramos, |
| Publisher : | N/A |
| Publication Date : | 1998 |
| ISSN : | N/A |
| Abstract : | We show that the well-known random incremental construction of Clarkson and Shor [14] can be adapted via gradations to provide efficient external-memory algorithms for some geometric problems. In particular, as the main result, we obtain an optimal randomized algorithm for the problem of computing the trapezoidal decomposition determined by a set of N line segments in the plane with K pairwise intersections, that requires \Theta( N, |