License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2020.63
URN: urn:nbn:de:0030-drops-122218
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12221/
Go to the corresponding LIPIcs Volume Portal

Phillips, Jeff M. ; Tang, Pingfan

Sketched MinDist

pdf-format:
LIPIcs-SoCG-2020-63.pdf (1.0 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{phillips_et_al:LIPIcs:2020:12221,
  author =	{Jeff M. Phillips and Pingfan Tang},
  title =	{{Sketched MinDist}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{63:1--63:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Sergio Cabello and Danny Z. Chen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12221},
  URN =		{urn:nbn:de:0030-drops-122218},
  doi =		{10.4230/LIPIcs.SoCG.2020.63},
  annote =	{Keywords: curve similarity, sensitivity sampling, sketching}
}

Keywords: curve similarity, sensitivity sampling, sketching
Collection: 36th International Symposium on Computational Geometry (SoCG 2020)
Issue Date: 2020
Date of publication: 08.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI