3 Search Results for "Mehrabi, Ali D."


Document
Track A: Algorithms, Complexity and Games
Approximate Nearest Neighbor for Curves - Simple, Efficient, and Deterministic

Authors: Arnold Filtser, Omrit Filtser, and Matthew J. Katz

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)


Abstract
In the (1+ε,r)-approximate near-neighbor problem for curves (ANNC) under some similarity measure δ, the goal is to construct a data structure for a given set 𝒞 of curves that supports approximate near-neighbor queries: Given a query curve Q, if there exists a curve C ∈ 𝒞 such that δ(Q,C)≤ r, then return a curve C' ∈ 𝒞 with δ(Q,C') ≤ (1+ε)r. There exists an efficient reduction from the (1+ε)-approximate nearest-neighbor problem to ANNC, where in the former problem the answer to a query is a curve C ∈ 𝒞 with δ(Q,C) ≤ (1+ε)⋅δ(Q,C^*), where C^* is the curve of 𝒞 most similar to Q. Given a set 𝒞 of n curves, each consisting of m points in d dimensions, we construct a data structure for ANNC that uses n⋅ O(1/ε)^{md} storage space and has O(md) query time (for a query curve of length m), where the similarity measure between two curves is their discrete Fréchet or dynamic time warping distance. Our method is simple to implement, deterministic, and results in an exponential improvement in both query time and storage space compared to all previous bounds. Further, we also consider the asymmetric version of ANNC, where the length of the query curves is k ≪ m, and obtain essentially the same storage and query bounds as above, except that m is replaced by k. Finally, we apply our method to a version of approximate range counting for curves and achieve similar bounds.

Cite as

Arnold Filtser, Omrit Filtser, and Matthew J. Katz. Approximate Nearest Neighbor for Curves - Simple, Efficient, and Deterministic. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 48:1-48:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{filtser_et_al:LIPIcs.ICALP.2020.48,
  author =	{Filtser, Arnold and Filtser, Omrit and Katz, Matthew J.},
  title =	{{Approximate Nearest Neighbor for Curves - Simple, Efficient, and Deterministic}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{48:1--48:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.48},
  URN =		{urn:nbn:de:0030-drops-124555},
  doi =		{10.4230/LIPIcs.ICALP.2020.48},
  annote =	{Keywords: polygonal curves, Fr\'{e}chet distance, dynamic time warping, approximation algorithms, (asymmetric) approximate nearest neighbor, range counting}
}
Document
Minimum Perimeter-Sum Partitions in the Plane

Authors: Mikkel Abrahamsen, Mark de Berg, Kevin Buchin, Mehran Mehr, and Ali D. Mehrabi

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)


Abstract
Let P be a set of n points in the plane. We consider the problem of partitioning P into two subsets P_1 and P_2 such that the sum of the perimeters of CH(P_1) and CH(P_2) is minimized, where CH(P_i) denotes the convex hull of P_i. The problem was first studied by Mitchell and Wynters in 1991 who gave an O(n^2) time algorithm. Despite considerable progress on related problems, no subquadratic time algorithm for this problem was found so far. We present an exact algorithm solving the problem in O(n log^4 n) time and a (1+e)-approximation algorithm running in O(n + 1/e^2 log^4(1/e)) time.

Cite as

Mikkel Abrahamsen, Mark de Berg, Kevin Buchin, Mehran Mehr, and Ali D. Mehrabi. Minimum Perimeter-Sum Partitions in the Plane. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 4:1-4:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2017.4,
  author =	{Abrahamsen, Mikkel and de Berg, Mark and Buchin, Kevin and Mehr, Mehran and Mehrabi, Ali D.},
  title =	{{Minimum Perimeter-Sum Partitions in the Plane}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.4},
  URN =		{urn:nbn:de:0030-drops-72048},
  doi =		{10.4230/LIPIcs.SoCG.2017.4},
  annote =	{Keywords: Computational geometry, clustering, minimum-perimeter partition, convex hull}
}
Document
Range-Clustering Queries

Authors: Mikkel Abrahamsen, Mark de Berg, Kevin Buchin, Mehran Mehr, and Ali D. Mehrabi

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)


Abstract
In a geometric k-clustering problem the goal is to partition a set of points in R^d into k subsets such that a certain cost function of the clustering is minimized. We present data structures for orthogonal range-clustering queries on a point set S: given a query box Q and an integer k > 2, compute an optimal k-clustering for the subset of S inside Q. We obtain the following results. * We present a general method to compute a (1+epsilon)-approximation to a range-clustering query, where epsilon>0 is a parameter that can be specified as part of the query. Our method applies to a large class of clustering problems, including k-center clustering in any Lp-metric and a variant of k-center clustering where the goal is to minimize the sum (instead of maximum) of the cluster sizes. * We extend our method to deal with capacitated k-clustering problems, where each of the clusters should not contain more than a given number of points. * For the special cases of rectilinear k-center clustering in R^1, and in R^2 for k = 2 or 3, we present data structures that answer range-clustering queries exactly.

Cite as

Mikkel Abrahamsen, Mark de Berg, Kevin Buchin, Mehran Mehr, and Ali D. Mehrabi. Range-Clustering Queries. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 5:1-5:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2017.5,
  author =	{Abrahamsen, Mikkel and de Berg, Mark and Buchin, Kevin and Mehr, Mehran and Mehrabi, Ali D.},
  title =	{{Range-Clustering Queries}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.5},
  URN =		{urn:nbn:de:0030-drops-72147},
  doi =		{10.4230/LIPIcs.SoCG.2017.5},
  annote =	{Keywords: Geometric data structures, clustering, k-center problem}
}
  • Refine by Author
  • 2 Abrahamsen, Mikkel
  • 2 Buchin, Kevin
  • 2 Mehr, Mehran
  • 2 Mehrabi, Ali D.
  • 2 de Berg, Mark
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 2 clustering
  • 1 (asymmetric) approximate nearest neighbor
  • 1 Computational geometry
  • 1 Fréchet distance
  • 1 Geometric data structures
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2017
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail