3 Search Results for "Eckstein, Lutz"

Document

DOI: 10.4230/LIPIcs.SoCG.2025.78

Efficient Greedy Discrete Subtrajectory Clustering

Authors: Ivor van der Hoog, Lara Ost, Eva Rotenberg, and Daniel Rutschmann

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract

We cluster a set of trajectories 𝒯 using subtrajectories of 𝒯. We require for a clustering C that any two subtrajectories (𝒯[a, b], 𝒯[c, d]) in a cluster have disjoint intervals [a,b] and [c, d]. Clustering quality may be measured by the number of clusters, the number of vertices of 𝒯 that are absent from the clustering, and by the Fréchet distance between subtrajectories in a cluster. A Δ-cluster of 𝒯 is a cluster 𝒫 of subtrajectories of 𝒯 with a centre P ∈ 𝒫, where all subtrajectories in 𝒫 have Fréchet distance at most Δ to P. Buchin, Buchin, Gudmundsson, Löffler and Luo present two O(n² + n m 𝓁)-time algorithms: SC(max, 𝓁, Δ, 𝒯) computes a single Δ-cluster where P has at least 𝓁 vertices and maximises the cardinality m of 𝒫. SC(m, max, Δ, 𝒯) computes a single Δ-cluster where 𝒫 has cardinality m and maximises the complexity 𝓁 of P. In this paper, which is a mixture of algorithms engineering and theoretical insights, we use such maximum-cardinality clusters in a greedy clustering algorithm. We first provide an efficient implementation of SC(max, 𝓁, Δ, 𝒯) and SC(m, max, Δ, 𝒯) that significantly outperforms previous implementations. Next, we use these functions as a subroutine in a greedy clustering algorithm, which performs well when compared to existing subtrajectory clustering algorithms on real-world data. Finally, we observe that, for fixed Δ and 𝒯, these two functions always output a point on the Pareto front of some bivariate function θ(𝓁, m). We design a new algorithm PSC(Δ, 𝒯) that in O(n² log⁴ n) time computes a 2-approximation of this Pareto front. This yields a broader set of candidate clusters, with comparable quality to the output of the previous functions. We show that using PSC(Δ, 𝒯) as a subroutine improves the clustering quality and performance even further.

Cite as

Ivor van der Hoog, Lara Ost, Eva Rotenberg, and Daniel Rutschmann. Efficient Greedy Discrete Subtrajectory Clustering. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 78:1-78:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{vanderhoog_et_al:LIPIcs.SoCG.2025.78,
  author =	{van der Hoog, Ivor and Ost, Lara and Rotenberg, Eva and Rutschmann, Daniel},
  title =	{{Efficient Greedy Discrete Subtrajectory Clustering}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{78:1--78:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.78},
  URN =		{urn:nbn:de:0030-drops-232308},
  doi =		{10.4230/LIPIcs.SoCG.2025.78},
  annote =	{Keywords: Algorithms engineering, Fr\'{e}chet distance, subtrajectory clustering}
}

Document

DOI: 10.4230/LITES.8.1.2

Micro- and Macroscopic Road Traffic Analysis using Drone Image Data

Authors: Friedrich Kruber, Eduardo Sánchez Morales, Robin Egolf, Jonas Wurst, Samarjit Chakraborty, and Michael Botsch

Published in: LITES, Volume 8, Issue 1 (2022): Special Issue on Embedded Systems for Computer Vision. Leibniz Transactions on Embedded Systems, Volume 8, Issue 1

Abstract

The current development in the drone technology, alongside with machine learning based image processing, open new possibilities for various applications. Thus, the market volume is expected to grow rapidly over the next years. The goal of this paper is to demonstrate the capabilities and limitations of drone based image data processing for the purpose of road traffic analysis. In the first part a method for generating microscopic traffic data is proposed. More precisely, the state of vehicles and the resulting trajectories are estimated. The method is validated by conducting experiments with reference sensors and proofs to achieve precise vehicle state estimation results. It is also shown, how the computational effort can be reduced by incorporating the tracking information into a neural network. A discussion on current limitations supplements the findings. By collecting a large number of vehicle trajectories, macroscopic statistics, such as traffic flow and density can be obtained from the data. In the second part, a publicly available drone based data set is analyzed to evaluate the suitability for macroscopic traffic modeling. The results show that the method is well suited for gaining detailed information about macroscopic statistics, such as traffic flow dependent time headway or lane change occurrences. In conclusion, this paper presents methods to exploit the remarkable opportunities of drone based image processing for joint macro- and microscopic traffic analysis.

Cite as

Friedrich Kruber, Eduardo Sánchez Morales, Robin Egolf, Jonas Wurst, Samarjit Chakraborty, and Michael Botsch. Micro- and Macroscopic Road Traffic Analysis using Drone Image Data. In LITES, Volume 8, Issue 1 (2022): Special Issue on Embedded Systems for Computer Vision. Leibniz Transactions on Embedded Systems, Volume 8, Issue 1, pp. 02:1-02:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{kruber_et_al:LITES.8.1.2,
  author =	{Kruber, Friedrich and S\'{a}nchez Morales, Eduardo and Egolf, Robin and Wurst, Jonas and Chakraborty, Samarjit and Botsch, Michael},
  title =	{{Micro- and Macroscopic Road Traffic Analysis using Drone Image Data}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{02:1--02:27},
  ISSN =	{2199-2002},
  year =	{2022},
  volume =	{8},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES.8.1.2},
  URN =		{urn:nbn:de:0030-drops-192898},
  doi =		{10.4230/LITES.8.1.2},
  annote =	{Keywords: traffic data analysis, trajectory data, drone image data}
}

Document

DOI: 10.4230/OASIcs.ASD.2020.4

Agile Requirement Engineering for a Cloud System for Automated and Networked Vehicles

Authors: Armin Mokhtarian, Alexandru Kampmann, Bassam Alrifaee, Stefan Kowalewski, Bastian Lampe, and Lutz Eckstein

Published in: OASIcs, Volume 79, 2nd International Workshop on Autonomous Systems Design (ASD 2020)

Abstract

This paper presents a methodology for the agile development of a cloud system in a multi-partner project centered around automated vehicles. Besides providing an external environment model as an additional input to the automation, the cloud system is also the main gateway for users to interact with automated vehicles through applications on mobile devices. Multiple factors are posing a challenge in our context. Coordination becomes especially challenging, as stakeholders are spread among different locations with backgrounds from various domains. Furthermore, automated vehicles for different applications, such as delivery or taxi services, give rise to a large number of use cases that our cloud system has to support. For our agile development process, we use standardized templates for the description of use-cases, which are initialized from storyboards and iteratively refined by stakeholders. These use-case templates are subsequently transformed into machine-readable specifications, which allows for generation of REST APIs for our cloud system.

Cite as

Armin Mokhtarian, Alexandru Kampmann, Bassam Alrifaee, Stefan Kowalewski, Bastian Lampe, and Lutz Eckstein. Agile Requirement Engineering for a Cloud System for Automated and Networked Vehicles. In 2nd International Workshop on Autonomous Systems Design (ASD 2020). Open Access Series in Informatics (OASIcs), Volume 79, pp. 4:1-4:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{mokhtarian_et_al:OASIcs.ASD.2020.4,
  author =	{Mokhtarian, Armin and Kampmann, Alexandru and Alrifaee, Bassam and Kowalewski, Stefan and Lampe, Bastian and Eckstein, Lutz},
  title =	{{Agile Requirement Engineering for a Cloud System for Automated and Networked Vehicles}},
  booktitle =	{2nd International Workshop on Autonomous Systems Design (ASD 2020)},
  pages =	{4:1--4:8},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-141-2},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{79},
  editor =	{Steinhorst, Sebastian and Deshmukh, Jyotirmoy V.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ASD.2020.4},
  URN =		{urn:nbn:de:0030-drops-125983},
  doi =		{10.4230/OASIcs.ASD.2020.4},
  annote =	{Keywords: agile requirements engineering, cloud architecture, automated vehicles}
}

Refine by Type
3 Document/PDF
1 Document/HTML

Refine by Publication Year
1 2025
1 2022
1 2020

Refine by Author
1 Alrifaee, Bassam
1 Botsch, Michael
1 Chakraborty, Samarjit
1 Eckstein, Lutz
1 Egolf, Robin
Show More...

Refine by Series/Journal
1 LIPIcs
1 OASIcs
1 LITES

Refine by Classification
1 Computing methodologies → Machine learning
1 Software and its engineering
1 Theory of computation → Computational geometry

Refine by Keyword
1 Algorithms engineering
1 Fréchet distance
1 agile requirements engineering
1 automated vehicles
1 cloud architecture
Show More...

3 Search Results for "Eckstein, Lutz"

Efficient Greedy Discrete Subtrajectory Clustering

Abstract

Cite as

Micro- and Macroscopic Road Traffic Analysis using Drone Image Data

Abstract

Cite as

Agile Requirement Engineering for a Cloud System for Automated and Networked Vehicles

Abstract

Cite as

Thanks for your feedback!

Could not send message