Berechnung der Ähnlichkeit von Geographischen Objekten
Final Report Abstract
In dieser Forschung wurden Algorithmen zur Bestimmung der Ähnlickelt von geographischen Objekten entwickelt. Geplant war es drei verschiedene Objekte zu betrachten: 1. Trajektorien: Sequenzen von Punkten in Zeit und Raum, welche die Bewegung eines Objektes beschreiben. 2. Temporale Punktmengen: Mengen von Punkten, die zeitdatiert sind. 3. Gelände: Diskrete Darstellung eines Geländes, z.B., in Form einer Triangulierung. Im Laufe der Forschung ergab sich, dass der Bereich der Ähnlichkeit und allgemeiner die Analyse von Trajektorien ein aktuell sehr relevantes Forschungsgebiet ist, in dem noch viele offene Fragen bestehen. Daher habe ich meine Forschung vor allem auf dieses Gebiet fokussiert und auf diesem mehrere interessante Ergebnisse erzielt. Insbesondere habe ich zwei Ähnlichkeitsmasse für Trajektorien studiert: a. Der durchschnittliche Abstand an gleichen Zeltpunkten. b. Der Fréchet Abstand: maximaler Abstand an unterschiedlichen Zeitpunkten, wobei eine Zuordnung zwischen den Zeitpunkten beider Trajektorien besteht, welche den Zeitverlauf verzerrt aber nicht die Abfolge vertauscht. Für beide Abstandsmasse habe ich, gemeinsam mit meinen Kollaboratoren, neue Definitionen und Algorithmen entwickelt, welche durch Probleme aus Anwendungsgebieten motiviert sind. Desweiteren habe ich Algorithmen zum Finden einer repräsentativen Trajektorien in einer Menge von ähnlichen Trajektorien und zum Segmentieren von Trajektorien entwickelt. Auf Punktmengen habe ich algorithmische Lösungen für das Clustern von aggregierten Daten und das Verbinden von Punkten in unvollständigen Netzwerken entwickelt. Für Gelände habe ich den Fréchet Abstand als Abstandsmass betrachtet. Unser ursprüngliches Ziel war, hierfür einen effizienten Algorithmus zu entwickeln. Wir haben dann allerdings gezeigt, dass es unwahrscheinlich ist, das sich der Fréchet Abstand von Geländen effizient berechnen lässt.
Publications
- Clusters in Aggregated Health Data. In Proc. 13th International Symposium on Spatial Data Handling (SDH), pages 77-90, 2008
K. Buchin, M. Buchin, M. van Kreveld, M. Löffier, J. Luo, R. I. Silveira
- Detecting commuting patterns by clustering subtrajectories. In Proc. 19th International Symposium on Algorithms and Computation (ISAAC), S. 644-65S, 2008
K. Buchin, M. Buchin, J. Gudmundsson, M. Löffier, and J. Luo
- Detecting single file movement. In Proc. 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS), S. 288-297, 2008
K. Buchin, M. Buchin, and J. Gudmundsson
- Connect the Dot: Computing Feed-links with Minimum Dilation. In Proc. 11th Algorithms and Data Structures Symposium (WADS), pages 49-60, 2009
B. Aronov, K. Buchin, M. Buchin, M. van Kreveld, M. Löffier, J. Luo, R. I. Silveira, and B. Speckmann
- Exact algorithm for partial curve matching via the Fréchet distance. In Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), S. 645-654, 2009
K. Buchin, M. Buchin, and Y. Wang
- Finding long and similar parts of trajectories. In Proc. 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS), S. 296-305, 2009
K. Buchin, M. Buchin, M. van Kreveld, and J. Luo
- Constrained free space diagrams: a tool for trajectory analysis. International Journal of Geographical Information Science (IJGIS), 24:1101-1125, 2010
K. Buchin, M. Buchin, and J. Gudmundsson
- Fréchet Distance of Surfaces: Some Simple Hard Cases. In Proc. 18th Annual European Symposium on Algorithms, part II Volume 6347, pages 63-74, 2010
K. Buchin, M. Buchin, and A. Schulz
- Median trajectories. In Proc. 18th Annual European Symposium on Algorithms (ESA), part I, LNCS 6346, S. 463-474, Springer, 2010
K. Buchin, M. Buchin, M. van Kreveld, M. Löffier, R. I. Silveira, C. Wenk, and L Wiratma
