Sketched MinDist

Abstract

We consider sketch vectors of geometric objects $J$ through the \mindist function \[ v_i(J) = \inf_{p \in J} \|p-q_i\| \] for $q_i\in Q$ from a point set $Q$. Collecting the vector of these sketch values induces a simple, effective, and powerful distance: the Euclidean distance between these sketched vectors. This paper shows how large this set $Q$ needs to be under a variety of shapes and scenarios. For hyperplanes we provide direct connection to the sensitivity sample framework, so relative error can be preserved in $d$ dimensions using $Q=O(d/{\epsilon }^2)$. However, for other shapes, we show we need to enforce a minimum distance parameter $\rho$, and a domain size $L$. For $d=2$ the sample size $Q$ then can be $\tilde{O}((L/\rho )\cdot 1/{\epsilon }^2)$. For objects (e.g., trajectories) with at most $k$ pieces this can provide stronger \emph{for all} approximations with $\tilde{O}((L/\rho )\cdot k^3/{\epsilon }^2)$ points. Moreover, with similar size bounds and restrictions, such trajectories can be reconstructed exactly using only these sketch vectors.