Sketched MinDist

We consider sketch vectors of geometric objects J through the mindist function [ vi(J) = infp ∈ J |p-qi| ] for qi ∈ 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/varepsilon2). However, for other shapes, we show we need to enforce a minimum distance parameter ρ, and a domain size L. For d=2 the sample size Q then can be tildeO((L/ρ) · 1/varepsilon2). For objects (e.g., trajectories) with at most k pieces this can provide stronger for all approximations with tildeO((L/ρ)· k3 / varepsilon2) points. Moreover, with similar size bounds and restrictions, such trajectories can be reconstructed exactly using only these sketch vectors.