Global Curve Simplification. Due to its many applications, emphcurve simplification is a longstudied problem in computational geometry and adjacent disciplines, such as graphics, geographical information science, etc. Given a polygonal curve P with n vertices, the goal is to find another polygonal curve Pu0027 with a smaller number of vertices such that Pu0027 is sufficiently similar to P. Quality guarantees of a simplification are usually given in a emphlocal sense, bounding the distance between a shortcut and its corresponding section of the curve. In this work, we aim to provide a systematic overview of curve simplification problems under emphglobal distance measures that bound the distance between P and Pu0027. We consider six different curve distance measures: three variants of the emphHausdorff distance and three variants of the emphFru0027echet distance. And we study different restrictions on the choice of vertices for Pu0027. We provide polynomialtime algorithms for some variants of the global curve simplification problem and show NPhardness for other variants. Through this systematic study we observe, for the first time, some surprising patterns, and suggest directions for future research in this important area.

Optimal Deterministic Shallow Cuttings for 3d Dominance Ranges Shallow cuttings are one of the most fundamental tools in range searching as many problems in the field admit efficient static data structures due to their application. We present the first efficient deterministic algorithms that, given n threedimensional points, construct optimalsize (single and multiple) shallow cuttings for orthogonal dominance ranges. Specifically, we show how to construct a single shallow cutting in                                                                           Oleft( nlog nright)                                                                          :138,290,worstcase time, using                                                                           Oleft( nright)                                                                          space. We also show that the same complexity suffices to construct simultaneously a logarithmic number of shallow cuttings on the input pointset. Our algorithms are optimal in the comparison and algebraiccomparison models, and constitute an important step forwards as the first improvement over previous deterministic polynomialtime guarantees by Matousek (Comput Geom 2(3):169xe2x80x93186, 1992) and Agarwal et al. (SIAM J Comput 29(3):912xe2x80x93953, 2000) matching the complexity of the optimal deteministic algorithm for the more general 3d halfspace ranges by Chan and Tsakalidis (Discrete Comput Geom 56(4):866xe2x80x93881, 2016). Our methods yield :138,290,worstcase efficient preprocessing algorithms for a series of important orthogonal range searching problems in the pointer machine and the wordRAM models, where such shallow cuttings are utilized to support queries efficiently.