Abstract We introduce a new embedding technique based on a nested barycentric coordinate system. We show that our embedding can be used to transform the problems of polyhedron approximation, piecewise linear classification and convex regression into one of finding a linear classifier or regressor in a higher dimensional (but nevertheless quite sparse) representation. Our embedding maps a piecewise linear function into an everywhere-linear function, and allows us to invoke well-known algorithms for the latter problem to solve the former. We explain the applications of our embedding to the problems of approximating separating polyhedra—in fact, it can approximate any convex body and unions of convex bodies—as well as to classification by separating polyhedra, and to piecewise linear regression.

Inspired by a mathematical riddle involving fuses, we define the "fusible numbers" as follows: $0$ is fusible, and whenever $x,y$ are fusible with $|y-x|<1$, the number $(x+y+1)/2$ is also fusible. We prove that the set of fusible numbers, ordered by the usual order on $\mathbb R$, is well-ordered, with order type $\varepsilon_0$. Furthermore, we prove that the density of the fusible numbers along the real line grows at an incredibly fast rate: Letting $g(n)$ be the largest gap between consecutive fusible numbers in the interval $[n,\infty)$, we have $g(n)^{-1} \ge F_{\varepsilon_0}(n-c)$ for some constant $c$, where $F_\alpha$ denotes the fast-growing hierarchy. Finally, we derive some true statements that can be formulated but not proven in Peano Arithmetic, of a different flavor than previously known such statements: PA cannot prove the true statement "For every natural number $n$ there exists a smallest fusible number larger than $n$." Also, consider the algorithm "$M(x)$: if $x<0$ return $-x$, else return $M(x-M(x-1))/2$." Then $M$ terminates on real inputs, although PA cannot prove the statement "$M$ terminates on all natural inputs."

We present an improved algorithm forquasi-properlylearning convex polyhedra in the realizable PAC setting from data with a margin. Our learning algorithm constructs a consistent polyhedron as an intersection of about$t \log t$halfspaces with constant-size margins in time polynomial in$t$(where$t$is the number of halfspaces forming an optimal polyhedron). We also identify distinct generalizations of the notion of margin from hyperplanes to polyhedra and investigate how they relate geometrically; this result may have ramifications beyond the learning setting.

We introduce a new embedding technique based on barycentric coordinate system. We show that our embedding can be used to transforms the problem of polytope approximation into that of finding a linear classifier in a higher (but nevertheless quite sparse) dimensional representation. This embedding in effect maps a piecewise linear function into a single linear function, and allows us to invoke well-known algorithms for the latter problem to solve the former. We demonstrate that our embedding has applications to the problems of approximating separating polytopes – in fact, it can approximate any convex body and multiple convex bodies – as well as to classification by separating polytopes and piecewise linear regression.

Inspired by a mathematical riddle involving fuses, we define the fusible numbers as follows: 0 is fusible, and whenever x, y are fusible with |y - x|- 1≥ Fε0(n - c) for some constant c, where Fα denotes the fast-growing hierarchy.Finally, we derive some true statements that can be formulated but not proven in Peano Arithmetic, of a different flavor than previously known such statements: PA cannot prove the true statement "For every natural number n there exists a smallest fusible number larger than n." Also, consider the algorithm "M(x): if x <; 0 return -x, else return M(x - M(x - 1))/2." Then M terminates on real inputs, although PA cannot prove the statement "M terminates on all natural inputs."

In this paper we study an experimentally-observed connection between two seemingly unrelated processes, one from computational geometry and the other from differential geometry. The first one (which we call grid peeling) is the convex-layer decomposition of subsets G ⊂ ℤ2 of the integer grid, previously studied for the particular case G = {1, …, m}2 by Har-Peled and Lidický (2013). The second one is the affine curve-shortening flow (ACSF), first studied by Alvarez et al. (1993) and Sapiro and Tannenbaum (1993). We present empirical evidence that, in a certain well-defined sense, grid peeling behaves at the limit like ACSF on convex curves. We offer some theoretical arguments in favor of this conjecture. We also pay closer attention to the simple case where G = ℕ2 is a quarter-infinite grid. This case corresponds to ACSF starting with an infinite L-shaped curve, which when transformed using the ACSF becomes a hyperbola for all times t > 0. We prove that, in the grid peeling of ℕ2, (1) the number of grid points removed up to iteration n is Θ(n3/2 log n); and (2) the boundary at iteration n is sandwiched between two hyperbolas that are separated from each other by a constant factor.

We present improved algorithm for properly learning convex polytopes in the realizable PAC setting from data with a margin. Our learning algorithm constructs a consistent polytope as an intersection of about t log t halfspaces with margins in time polynomial in t (where t is the number of halfspaces forming an optimal polytope). We also identify distinct generalizations of the notion of margin from hyperplanes to polytopes and investigate how they relate geometrically; this result may be of interest beyond the learning setting.

We present several new results regarding λ s ( n ), the maximum length of a Davenport--Schinzel sequence of order s on n distinct symbols. First, we prove that λ s ( n ) ≤ n · 2 (1/ t !)α( n ) t + O (α( n ) t -1 ) for s ≥ 4 even, and λ s ( n ) ≤ n · 2 (1/t!)α( n ) t log 2 α( n ) + O (α( n ) t ) for s ≥ 3 odd, where t = ⌊( s -2)/2⌋, and α( n ) denotes the inverse Ackermann function. The previous upper bounds, by Agarwal et al. [1989], had a leading coefficient of 1 instead of 1/ t ! in the exponent. The bounds for even s are now tight up to lower-order terms in the exponent. These new bounds result from a small improvement on the technique of Agarwal et al. More importantly, we also present a new technique for deriving upper bounds for λ s ( n ). This new technique is very similar to the one we applied to the problem of stabbing interval chains [Alon et al. 2008]. With this new technique we: (1) re-derive the upper bound of λ 3 ( n ) ≤ 2 n α( n ) + O ( n √α( n )) (first shown by Klazar [1999]); (2) re-derive our own new upper bounds for general s and (3) obtain improved upper bounds for the generalized Davenport--Schinzel sequences considered by Adamec et al. [1992]. Regarding lower bounds, we show that λ 3 ( n ) ≥ 2 n α( n ) - O ( n ) (the previous lower bound (Sharir and Agarwal, 1995) had a coefficient of 1/2), so the coefficient 2 is tight. We also present a simpler variant of the construction of Agarwal et al. [1989] that achieves the known lower bounds of λ s ( n ) ≥ n · 2 (1/ t !) α( n ) t - O (α( n ) t -1 ) for s ≥ 4 even.

A set N ⊂ Rd is called a weak ε-net (with respect to convex sets) for a finite X ⊂ Rd if N intersects every convex set C with |X ∩ C|≥ε|X|. For every fixed d≥ 2 and every r≥ 1 we construct sets X⊂ Rd for which every weak 1/r-net has at least Ω(r logd-1 r) points; this is the first superlinear lower bound for weak ε-nets in a fixed dimension.

We present several new results regarding λs(n), the maximum length of a Davenport–Schinzel sequence of order s on n distinct symbols. First, we prove that where t = [(s − 2)/2], and α(n) denotes the inverse Ackermann function. The previous upper bounds, by Agarwal, Sharir, and Shor (1989), had a leading coefficient of 1 instead of 1/t! in the exponent. The bounds for even s are now tight up to lower-order terms in the exponent. These new bounds result from a small improvement on the technique of Agarwal et al. More importantly, we also present a new technique for deriving upper bounds for λs(n). This new technique is based on some recurrences very similar to those used by the author, together with Alon, Kaplan, Sharir, and Smorodinsky (SODA 2008), for the problem of stabbing interval chains with j-tuples. With this new technique we: (1) re-derive the upper bound of λ3(n) ≤ (first shown by Klazar, 1999); (2) re-derive our own new upper bounds for general s; and (3) obtain improved upper bounds for the generalized Davenport–Schinzel sequences considered by Adamec, Klazar, and Valtr (1992). Regarding lower bounds, we show that λ3(n) ≥ 2nα(n) – O(n) (the previous lower bound (Sharir and Agarwal, 1995) had a coefficient of ½), so the coefficient 2 is tight. We also present a simpler variant of the construction of Agarwal, Sharir, and Shor that achieves the known lower bounds of for s ≥ 4 even.

We construct weak ε-nets of almost linear size for certain types of point sets. Specifically, for planar point sets in convex position we construct weak 1/r-nets of size O(rα(r)), where α(r) denotes the inverse Ackermann function. For point sets along the moment curve in ℝ d we construct weak 1/r-nets of size r · 2 poly(α(r)) , where the degree of the polynomial in the exponent depends (quadratically) on d. Our constructions result from a reduction to a new problem, which we call stabbing interval chains with j-tuples. Given the range of integers N = [1, n], an interval chain of length k is a sequence of k consecutive, disjoint, nonempty intervals contained in N. A j-tuple $\bar{P}$ = (p1,…,pj) is said to stab an interval chain C = I 1 …I k if each p i falls on a different interval of C. The problem is to construct a small-size family Z of j-tuples that stabs all k-interval chains in N. Let z (j) k (n) denote the minimum size of such a family Z. We derive almost-tight upper and lower bounds for z (j) k (n) for every fixed j; our bounds involve functions α m (n) of the inverse Ackermann hierarchy. Specifically, we show that for j = 3 we have z (3) k (n) = Θ(nα $\lfloor$k/2$\rfloor$ (n)) for all k ≥ 6. For each j≥4, we construct a pair of functions Pʹ j (m), Qʹ j (m), almost equal asymptotically, such that z (j) Pʹ j(m)(n) = O(nα m (n)) and z (j) Qʹ j(m)(n) = Ω(nα m (n)).