### Abstract

The Euclidean k-Center problem is a classical problem that has been extensively studied in computer science. Given a set G of n points in Euclidean space, the problem is to determine a set C of k centers (not necessarily part of G) such that the maximum distance between a point in G and its nearest neighbor in C is minimized. In this paper we study the corresponding (k, ℓ)-CENTER problem for polygonal curves under the Fréchet distance, that is, given a set G of n polygonal curves in ℝd, each of complexity m, determine a set C of k polygonal curves in ℝd, each of complexity ℓ, such that the maximum Fréchet distance of a curve in G to its closest curve in C is minimized. In their 2016 paper, Driemel, Krivošija, and Sohler give a near-linear time (1 + ε-approximation algorithm for one-dimensional curves, assuming that k and ℓ are constants. In this paper, we substantially extend and improve the known approximation bounds for curves in dimension 2 and higher. Our analysis thus extends to application-relevant input data such as GPS-trajectories and protein backbones. We show that, if ℓ is part of the input, then there is no polynomial-time approximation scheme unless P = NP. Our constructions yield different bounds for one and two-dimensional curves and the discrete and continuous Fréchet distance. In the case of the discrete Fréchet distance on two-dimensional curves, we show hardness of approximation within a factor close to 2.598. This result also holds when k = 1, and the NP-hardness extends to the case that ℓ = ∞, i.e., for the problem of computing the minimum-enclosing ball under the Fréchet distance. Finally, we observe that a careful adaptation of Gonzalez’ algorithm in combination with a curve simplification yields a 3-approximation in any dimension, provided that an optimal simplification can be computed exactly. We conclude that our approximation bounds are close to being tight.

Read More: https://epubs.siam.org/doi/10.1137/1.9781611975482.181

Original language | English |
---|---|

Title of host publication | 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) |

Editors | Timothy M. Chan |

Publisher | Society for Industrial and Applied Mathematics (SIAM) |

Pages | 2922-2938 |

Number of pages | 17 |

ISBN (Electronic) | 978-1-61197-548-2 |

DOIs | |

Publication status | Published - 2 Jan 2019 |

Event | ACM-SIAM Symposium on Discrete Algorithms (SODA2019) - San Diego, United States Duration: 6 Jan 2019 → 9 Jan 2019 https://www.siam.org/Conferences/CM/Conference/soda19 |

### Conference

Conference | ACM-SIAM Symposium on Discrete Algorithms (SODA2019) |
---|---|

Abbreviated title | SODA2019 |

Country | United States |

City | San Diego |

Period | 6/01/19 → 9/01/19 |

Internet address |

### Fingerprint

### Cite this

*30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*(pp. 2922-2938). Society for Industrial and Applied Mathematics (SIAM). https://doi.org/10.1137/1.9781611975482.181

}

*30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).*Society for Industrial and Applied Mathematics (SIAM), pp. 2922-2938, ACM-SIAM Symposium on Discrete Algorithms (SODA2019), San Diego, United States, 6/01/19. https://doi.org/10.1137/1.9781611975482.181

**Approximating (k,ℓ)-center clustering for curves.** / Buchin, Kevin; Driemel, Anne; Gudmundsson, Joachim; Horton, Michael; Kostitsyna, Irina; Löffler, Maarten; Struijs, Martijn.

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

TY - CHAP

T1 - Approximating (k,ℓ)-center clustering for curves

AU - Buchin, Kevin

AU - Driemel, Anne

AU - Gudmundsson, Joachim

AU - Horton, Michael

AU - Kostitsyna, Irina

AU - Löffler, Maarten

AU - Struijs, Martijn

PY - 2019/1/2

Y1 - 2019/1/2

N2 - The Euclidean k-Center problem is a classical problem that has been extensively studied in computer science. Given a set G of n points in Euclidean space, the problem is to determine a set C of k centers (not necessarily part of G) such that the maximum distance between a point in G and its nearest neighbor in C is minimized. In this paper we study the corresponding (k, ℓ)-CENTER problem for polygonal curves under the Fréchet distance, that is, given a set G of n polygonal curves in ℝd, each of complexity m, determine a set C of k polygonal curves in ℝd, each of complexity ℓ, such that the maximum Fréchet distance of a curve in G to its closest curve in C is minimized. In their 2016 paper, Driemel, Krivošija, and Sohler give a near-linear time (1 + ε-approximation algorithm for one-dimensional curves, assuming that k and ℓ are constants. In this paper, we substantially extend and improve the known approximation bounds for curves in dimension 2 and higher. Our analysis thus extends to application-relevant input data such as GPS-trajectories and protein backbones. We show that, if ℓ is part of the input, then there is no polynomial-time approximation scheme unless P = NP. Our constructions yield different bounds for one and two-dimensional curves and the discrete and continuous Fréchet distance. In the case of the discrete Fréchet distance on two-dimensional curves, we show hardness of approximation within a factor close to 2.598. This result also holds when k = 1, and the NP-hardness extends to the case that ℓ = ∞, i.e., for the problem of computing the minimum-enclosing ball under the Fréchet distance. Finally, we observe that a careful adaptation of Gonzalez’ algorithm in combination with a curve simplification yields a 3-approximation in any dimension, provided that an optimal simplification can be computed exactly. We conclude that our approximation bounds are close to being tight.Read More: https://epubs.siam.org/doi/10.1137/1.9781611975482.181

AB - The Euclidean k-Center problem is a classical problem that has been extensively studied in computer science. Given a set G of n points in Euclidean space, the problem is to determine a set C of k centers (not necessarily part of G) such that the maximum distance between a point in G and its nearest neighbor in C is minimized. In this paper we study the corresponding (k, ℓ)-CENTER problem for polygonal curves under the Fréchet distance, that is, given a set G of n polygonal curves in ℝd, each of complexity m, determine a set C of k polygonal curves in ℝd, each of complexity ℓ, such that the maximum Fréchet distance of a curve in G to its closest curve in C is minimized. In their 2016 paper, Driemel, Krivošija, and Sohler give a near-linear time (1 + ε-approximation algorithm for one-dimensional curves, assuming that k and ℓ are constants. In this paper, we substantially extend and improve the known approximation bounds for curves in dimension 2 and higher. Our analysis thus extends to application-relevant input data such as GPS-trajectories and protein backbones. We show that, if ℓ is part of the input, then there is no polynomial-time approximation scheme unless P = NP. Our constructions yield different bounds for one and two-dimensional curves and the discrete and continuous Fréchet distance. In the case of the discrete Fréchet distance on two-dimensional curves, we show hardness of approximation within a factor close to 2.598. This result also holds when k = 1, and the NP-hardness extends to the case that ℓ = ∞, i.e., for the problem of computing the minimum-enclosing ball under the Fréchet distance. Finally, we observe that a careful adaptation of Gonzalez’ algorithm in combination with a curve simplification yields a 3-approximation in any dimension, provided that an optimal simplification can be computed exactly. We conclude that our approximation bounds are close to being tight.Read More: https://epubs.siam.org/doi/10.1137/1.9781611975482.181

UR - http://www.scopus.com/inward/record.url?scp=85066951960&partnerID=8YFLogxK

U2 - 10.1137/1.9781611975482.181

DO - 10.1137/1.9781611975482.181

M3 - Chapter

SP - 2922

EP - 2938

BT - 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

A2 - Chan, Timothy M.

PB - Society for Industrial and Applied Mathematics (SIAM)

ER -