Handbook of Data Structures and Applications, 2nd Edition

26

Cuttings^*

Bernard Chazelle

Princeton University

26.1Introduction

26.2The Cutting Construction

Geometric Sampling•Optimal Cuttings

26.3Applications

Point Location•Hopcroft’s Problem•Convex Hulls and Voronoi Diagrams•Range Searching

Acknowledgments

References

26.1Introduction

For divide-and-conquer purposes, it is often desirable to organize a set S of n numbers into a sorted list, or perhaps to partition it into two equal-sized groups with no element in one group exceeding any element in the other one. More generally, we might wish to break up S into k groups of size roughly n/k, with again a total ordering among the distinct groups. In the first case we sort; in the second one we compute the median; in the third one we compute quantiles. ...