Sketched MinDist

We sketch geometric objects J as vectors through the MinDist function, setting the i-th coordinate v_i(J) = inf_{p ∈ J} ‖p-q_i‖ for q_i ∈ Q from a point set Q. Building a vector from these coordinate values induces a simple, effective, and powerful distance: the Euclidean distance between these sketch 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 sampling framework, so relative error can be preserved in d dimensions using |Q| = O(d/ε²). 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 Õ((L/ρ) ⋅ 1/ε²). For objects (e.g., trajectories) with at most k pieces this can provide stronger for all approximations with Õ((L/ρ)⋅ k³ / ε²) points. Moreover, with similar size bounds and restrictions, such trajectories can be reconstructed exactly using only these sketch vectors. Cumulatively, these results demonstrate that these MinDist sketch vectors provide an effective and efficient shape model, a compact representation, and a precise representation of geometric objects.