DROPS

Document

DOI: 10.4230/LIPIcs.SWAT.2024.2

Local Spanners Revisited

Authors: Stav Ashur and Sariel Har-Peled

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract

For a set P ⊆ ℝ² of points and a family ℱ of regions, a local t-spanner of P is a sparse graph G over P, such that for any region r ∈ ℱ the subgraph restricted to r, denoted by G ∩ r, is a t-spanner for all the points of r ∩ P. We present algorithms for the construction of local spanners with respect to several families of regions such as homothets of a convex region. Unfortunately, the number of edges in the resulting graph depends logarithmically on the spread of the input point set. We prove that this dependency cannot be removed, thus settling an open problem raised by Abam and Borouny. We also show improved constructions (with no dependency on the spread) of local spanners for fat triangles, and regular k-gons. In particular, this improves over the known construction for axis-parallel squares. We also study notions of weaker local spanners where one is allowed to shrink the region a "bit". Surprisingly, we show a near linear-size construction of a weak spanner for axis-parallel rectangles, where the shrinkage is multiplicative. Any spanner is a weak local spanner if the shrinking is proportional to the diameter of the region.

Cite as

Stav Ashur and Sariel Har-Peled. Local Spanners Revisited. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ashur_et_al:LIPIcs.SWAT.2024.2,
  author =	{Ashur, Stav and Har-Peled, Sariel},
  title =	{{Local Spanners Revisited}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{2:1--2:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.2},
  URN =		{urn:nbn:de:0030-drops-200420},
  doi =		{10.4230/LIPIcs.SWAT.2024.2},
  annote =	{Keywords: Geometric graphs, Fault-tolerant spanners}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2021.12

On Undecided LP, Clustering and Active Learning

Authors: Stav Ashur and Sariel Har-Peled

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract

We study colored coverage and clustering problems. Here, we are given a colored point set, where the points are covered by k (unknown) clusters, which are monochromatic (i.e., all the points covered by the same cluster have the same color). The access to the colors of the points (or even the points themselves) is provided indirectly via various oracle queries (such as nearest neighbor, or separation queries). We show that one can correctly deduce the color of all the points (i.e., compute a monochromatic clustering of the points) using a polylogarithmic number of queries, if the number of clusters is a constant. We investigate several variants of this problem, including Undecided Linear Programming and covering of points by k monochromatic balls.

Cite as

Stav Ashur and Sariel Har-Peled. On Undecided LP, Clustering and Active Learning. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ashur_et_al:LIPIcs.SoCG.2021.12,
  author =	{Ashur, Stav and Har-Peled, Sariel},
  title =	{{On Undecided LP, Clustering and Active Learning}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{12:1--12:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.12},
  URN =		{urn:nbn:de:0030-drops-138116},
  doi =		{10.4230/LIPIcs.SoCG.2021.12},
  annote =	{Keywords: Linear Programming, Active learning, Classification}
}

Search Results

Documents authored by Ashur, Stav

Local Spanners Revisited

Abstract

Cite as

On Undecided LP, Clustering and Active Learning

Abstract

Cite as

Thanks for your feedback!

Could not send message