3 Search Results for "Durocher, Stephane"

Document
DOI: 10.4230/LIPIcs.SWAT.2020.22
Clustering Moving Entities in Euclidean Space

Authors: Stephane Durocher and Md Yeakub Hassan

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Abstract
Clustering is a fundamental problem of spatio-temporal data analysis. Given a set 𝒳 of n moving entities, each of which corresponds to a sequence of τ time-stamped points in ℝ^d, a k-clustering of 𝒳 is a partition of 𝒳 into k disjoint subsets that optimizes a given objective function. In this paper, we consider two clustering problems, k-Center and k-MM, where the goal is to minimize the maximum value of the objective function over the duration of motion for the worst-case input 𝒳. We show that both problems are NP-hard when k is an arbitrary input parameter, even when the motion is restricted to ℝ. We provide an exact algorithm for the 2-MM clustering problem in ℝ^d that runs in O(τ d n²) time. The running time can be improved to O(τ n log{n}) when the motion is restricted to ℝ. We show that the 2-Center clustering problem is NP-hard in ℝ². Our 2-MM clustering algorithm provides a 1.15-approximate solution to the 2-Center clustering problem in ℝ². Moreover, finding a (1.15-ε)-approximate solution remains NP-hard for any ε >0. For both the k-MM and k-Center clustering problems in ℝ^d, we provide a 2-approximation algorithm that runs in O(τ d n k) time.
Cite as

Stephane Durocher and Md Yeakub Hassan. Clustering Moving Entities in Euclidean Space. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{durocher_et_al:LIPIcs.SWAT.2020.22,
  author =	{Durocher, Stephane and Hassan, Md Yeakub},
  title =	{{Clustering Moving Entities in Euclidean Space}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{22:1--22:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.22},
  URN =		{urn:nbn:de:0030-drops-122698},
  doi =		{10.4230/LIPIcs.SWAT.2020.22},
  annote =	{Keywords: trajectories, clustering, moving entities, k-CENTER, algorithms}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.10
Relating Graph Thickness to Planar Layers and Bend Complexity

Authors: Stephane Durocher and Debajyoti Mondal

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
The thickness of a graph G = (V, E) with n vertices is the minimum number of planar subgraphs of G whose union is G. A polyline drawing of G in R^2 is a drawing Gamma of G, where each vertex is mapped to a point and each edge is mapped to a polygonal chain. Bend and layer complexities are two important aesthetics of such a drawing. The bend complexity of Gamma is the maximum number of bends per edge in Gamma, and the layer complexity of Gamma is the minimum integer r such that the set of polygonal chains in Gamma can be partitioned into r disjoint sets, where each set corresponds to a planar polyline drawing. Let G be a graph of thickness t. By Fáry’s theorem, if t = 1, then G can be drawn on a single layer with bend complexity 0. A few extensions to higher thickness are known, e.g., if t = 2 (resp., t > 2), then G can be drawn on t layers with bend complexity 2 (resp., 3n + O(1)). In this paper we present an elegant extension of Fáry's theorem to draw graphs of thickness t > 2. We first prove that thickness-t graphs can be drawn on t layers with 2.25n + O(1) bends per edge. We then develop another technique to draw thickness-t graphs on t layers with reduced bend complexity for small values of t, e.g., for t in {3, 4}, the bend complexity decreases to O(sqrt(n)). Previously, the bend complexity was not known to be sublinear for t > 2. Finally, we show that graphs with linear arboricity k can be drawn on k layers with bend complexity 3*(k-1)*n/(4k-2).
Cite as

Stephane Durocher and Debajyoti Mondal. Relating Graph Thickness to Planar Layers and Bend Complexity. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 10:1-10:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{durocher_et_al:LIPIcs.ICALP.2016.10,
  author =	{Durocher, Stephane and Mondal, Debajyoti},
  title =	{{Relating Graph Thickness to Planar Layers and Bend Complexity}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{10:1--10:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.10},
  URN =		{urn:nbn:de:0030-drops-62767},
  doi =		{10.4230/LIPIcs.ICALP.2016.10},
  annote =	{Keywords: Graph Drawing, Thickness, Geometric Thickness, Layers; Bends}
}
Document
DOI: 10.4230/LIPIcs.STACS.2012.290
Linear-Space Data Structures for Range Mode Query in Arrays

Authors: Timothy M. Chan, Stephane Durocher, Kasper Green Larsen, Jason Morrison, and Bryan T. Wilkinson

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
A mode of a multiset S is an element a in S of maximum multiplicity; that is, a occurs at least as frequently as any other element in S. Given an array A[1:n] of n elements, we consider a basic problem: constructing a static data structure that efficiently answers range mode queries on A. Each query consists of an input pair of indices (i, j) for which a mode of A[i:j] must be returned. The best previous data structure with linear space, by Krizanc, Morin, and Smid (ISAAC 2003), requires O(sqrt(n) loglog n) query time. We improve their result and present an O(n)-space data structure that supports range mode queries in O(sqrt(n / log n)) worst-case time. Furthermore, we present strong evidence that a query time significantly below sqrt(n) cannot be achieved by purely combinatorial techniques; we show that boolean matrix multiplication of two sqrt(n) by sqrt(n) matrices reduces to n range mode queries in an array of size O(n). Additionally, we give linear-space data structures for orthogonal range mode in higher dimensions (queries in near O(n^(1-1/2d)) time) and for halfspace range mode in higher dimensions (queries in O(n^(1-1/d^2)) time).
Cite as

Timothy M. Chan, Stephane Durocher, Kasper Green Larsen, Jason Morrison, and Bryan T. Wilkinson. Linear-Space Data Structures for Range Mode Query in Arrays. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 290-301, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.STACS.2012.290,
  author =	{Chan, Timothy M. and Durocher, Stephane and Larsen, Kasper Green and Morrison, Jason and Wilkinson, Bryan T.},
  title =	{{Linear-Space Data Structures for Range Mode Query in Arrays}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{290--301},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.290},
  URN =		{urn:nbn:de:0030-drops-34254},
  doi =		{10.4230/LIPIcs.STACS.2012.290},
  annote =	{Keywords: mode, range query, data structure, linear space, array}
}
  • Refine by Author
  • 3 Durocher, Stephane
  • 1 Chan, Timothy M.
  • 1 Hassan, Md Yeakub
  • 1 Larsen, Kasper Green
  • 1 Mondal, Debajyoti
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Facility location and clustering

  • Refine by Keyword
  • 1 Geometric Thickness
  • 1 Graph Drawing
  • 1 Layers; Bends
  • 1 Thickness
  • 1 algorithms
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2012
  • 1 2016
  • 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact