$renewcommand{Re}{mathbb{R}}$Given a set $P$ of $n$ points in $Re^d$, consider the problem of computing $k$ subsets of $P$ that form clusters that are well-separated from each other, and each of them is large (cardinality wise). We provide tight uppe
r and lower bounds, and corresponding algorithms, on the quality of separation, and the size of the clusters that can be computed, as a function of $n,d,k,s$, and $Phi$, where $s$ is the desired separation, and $Phi$ is the spread of the point set $P$.
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 decomposi
tion of subsets $Gsubset mathbb Z^2$ of the integer grid, previously studied for the particular case $G={1,ldots,m}^2$ by Har-Peled and Lidicky (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=mathbb N^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 $mathbb N^2$, (1) the number of grid points removed up to iteration $n$ is $Theta(n^{3/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.
A graph drawn in the plane with n vertices is k-fan-crossing free for k > 1 if there are no k+1 edges $g,e_1,...e_k$, such that $e_1,e_2,...e_k$ have a common endpoint and $g$ crosses all $e_i$. We prove a tight bound of 4n-8 on the maximum number of
edges of a 2-fan-crossing free graph, and a tight 4n-9 bound for a straight-edge drawing. For k > 2, we prove an upper bound of 3(k-1)(n-2) edges. We also discuss generalizations to monotone graph properties.
