Median trajectories

K. Buchin, M. Buchin, M.J. Kreveld, van, M. Löffler, R.I. Silveira, C. Wenk, L. Wiratma

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

12 Citaten (Scopus)
2 Downloads (Pure)


We investigate the concept of a median among a set of trajectories. We establish criteria that a "median trajectory" should meet, and present two different methods to construct a median for a set of input trajectories. The first method is very simple, while the second method is more complicated and uses homotopy with respect to sufficiently large faces in the arrangement formed by the trajectories. We give algorithms for both methods, analyze the worst-case running time, and show that under certain assumptions both methods can be implemented efficiently. We empirically compare the output of both methods on randomly generated trajectories, and analyze whether the two methods yield medians that are according to our intuition. Our results suggest that the second method, using homotopy, performs considerably better.
Originele taal-2Engels
TitelAlgorithms - ESA 2010 (18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings. Part I)
RedacteurenM. Berg, de, U. Meyer
Plaats van productieBerlin
ISBN van geprinte versie978-3-642-15774-5
StatusGepubliceerd - 2010

Publicatie series

NaamLecture Notes in Computer Science
ISSN van geprinte versie0302-9743

Vingerafdruk Duik in de onderzoeksthema's van 'Median trajectories'. Samen vormen ze een unieke vingerafdruk.

Citeer dit