DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2017.39

Dominance Product and High-Dimensional Closest Pair under L_infty

Authors: Omer Gold and Micha Sharir

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract

Given a set $S$ of $n$ points in \mathbb{R}^d, the Closest Pair problem is to find a pair of distinct points in S at minimum distance. When d is constant, there are efficient algorithms that solve this problem, and fast approximate solutions for general d. However, obtaining an exact solution in very high dimensions seems to be much less understood. We consider the high-dimensional L_\infty Closest Pair problem, where d=n^r for some r > 0, and the underlying metric is L_\infty. We improve and simplify previous results for L_\infty Closest Pair, showing that it can be solved by a deterministic strongly-polynomial algorithm that runs in O(DP(n,d)\log n) time, and by a randomized algorithm that runs in O(DP(n,d)) expected time, where DP(n,d) is the time bound for computing the dominance product for n points in \mathbb{R}^d. That is a matrix D, such that D[i,j] = \bigl| \{k \mid p_i[k] \leq p_j[k]\} \bigr|; this is the number of coordinates at which p_j dominates p_i. For integer coordinates from some interval [-M, M], we obtain an algorithm that runs in \tilde{O}\left(\min\{Mn^{\omega(1,r,1)},\, DP(n,d)\}\right) time, where \omega(1,r,1) is the exponent of multiplying an n \times n^r matrix by an n^r \times n matrix. We also give slightly better bounds for DP(n,d), by using more recent rectangular matrix multiplication bounds. Computing the dominance product itself is an important task, since it is applied in many algorithms as a major black-box ingredient, such as algorithms for APBP (all pairs bottleneck paths), and variants of APSP (all pairs shortest paths).

Cite as

Omer Gold and Micha Sharir. Dominance Product and High-Dimensional Closest Pair under L_infty. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 39:1-39:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gold_et_al:LIPIcs.ISAAC.2017.39,
  author =	{Gold, Omer and Sharir, Micha},
  title =	{{Dominance Product and High-Dimensional Closest Pair under L\underlineinfty}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{39:1--39:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.39},
  URN =		{urn:nbn:de:0030-drops-82268},
  doi =		{10.4230/LIPIcs.ISAAC.2017.39},
  annote =	{Keywords: Closest Pair, Dominance Product, L\underlineinfty Proximity, Rectangular Matrix Multiplication}
}

Document

DOI: 10.4230/LIPIcs.ESA.2017.42

Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy

Authors: Omer Gold and Micha Sharir

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract

Given a set of n real numbers, the 3SUM problem is to decide whether there are three of them that sum to zero. Until a recent breakthrough by Gronlund and Pettie [FOCS'14], a simple Theta(n^2)-time deterministic algorithm for this problem was conjectured to be optimal. Over the years many algorithmic problems have been shown to be reducible from the 3SUM problem or its variants, including the more generalized forms of the problem, such as k-SUM and k-variate linear degeneracy testing (k-LDT). The conjectured hardness of these problems have become extremely popular for basing conditional lower bounds for numerous algorithmic problems in P. In this paper, we show that the randomized 4-linear decision tree complexity of 3SUM is O(n^{3/2}), and that the randomized (2k-2)-linear decision tree complexity of k-SUM and k-LDT is O(n^{k/2}), for any odd >= 3. These bounds improve (albeit randomized) the corresponding O(n^{3/2} sqrt{log n}) and O(n^{k/2} sqrt{log n}) decision tree bounds obtained by Gr{\o}nlund and Pettie. Our technique includes a specialized randomized variant of fractional cascading data structure. Additionally, we give another deterministic algorithm for 3SUM that runs in O(n^2 log log n / log n ) time. The latter bound matches a recent independent bound by Freund [Algorithmica 2017], but our algorithm is somewhat simpler, due to a better use of the word-RAM model.

Cite as

Omer Gold and Micha Sharir. Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 42:1-42:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gold_et_al:LIPIcs.ESA.2017.42,
  author =	{Gold, Omer and Sharir, Micha},
  title =	{{Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{42:1--42:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.42},
  URN =		{urn:nbn:de:0030-drops-78364},
  doi =		{10.4230/LIPIcs.ESA.2017.42},
  annote =	{Keywords: 3SUM, k-SUM, Linear Degeneracy, Linear Decision Trees, Fractional Cascading}
}

Document

DOI: 10.4230/LIPIcs.ICALP.2017.25

Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier

Authors: Omer Gold and Micha Sharir

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract

Dynamic Time Warping (DTW) and Geometric Edit Distance (GED) are basic similarity measures between curves or general temporal sequences (e.g., time series) that are represented as sequences of points in some metric space (X, dist). The DTW and GED measures are massively used in various fields of computer science and computational biology, consequently, the tasks of computing these measures are among the core problems in P. Despite extensive efforts to find more efficient algorithms, the best-known algorithms for computing the DTW or GED between two sequences of points in X = R^d are long-standing dynamic programming algorithms that require quadratic runtime, even for the one-dimensional case d = 1, which is perhaps one of the most used in practice. In this paper, we break the nearly 50 years old quadratic time bound for computing DTW or GED between two sequences of n points in R, by presenting deterministic algorithms that run in O( n^2 log log log n / log log n ) time. Our algorithms can be extended to work also for higher dimensional spaces R^d, for any constant d, when the underlying distance-metric dist is polyhedral (e.g., L_1, L_infty).

Cite as

Omer Gold and Micha Sharir. Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gold_et_al:LIPIcs.ICALP.2017.25,
  author =	{Gold, Omer and Sharir, Micha},
  title =	{{Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{25:1--25:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.25},
  URN =		{urn:nbn:de:0030-drops-73820},
  doi =		{10.4230/LIPIcs.ICALP.2017.25},
  annote =	{Keywords: Dynamic Time Warping, Geometric Edit Distance, Time Series, Points Matching, Geometric Matching}
}

3 Search Results for "Gold, Omer"

Dominance Product and High-Dimensional Closest Pair under L_infty

Abstract

Cite as

Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy

Abstract

Cite as

Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier

Abstract

Cite as

Thanks for your feedback!

Could not send message