Marc van Kreveld

Marc van Kreveld

Auto-generated profile, based on publicly available information

Marc van Kreveld

Utrecht University

Research Focus & Metrics

Academic Career Length

29Years (1998-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
4 March 2008 in Algorithmica
Verified
Journal Article
Open access
PDF file
MLMaarten Löffler
Maarten Löffler
MKMarc van Kreveld
Marc van Kreveld
Assume that a set of imprecise points is given, where each point is specified by a region in which the point may lie. We study the problem of computing the smallest and largest possible convex hulls, measured by length and by area. Generally we assume the imprecision region to be a square, but we discuss the case where it is a segment or circle as well. We give polynomial time algorithms for several variants of this problem, ranging in running time from O(nlog n) to O(n 13), and prove NP-hardness for some other variants.

20 January 2007 in GeoInformatica
Verified
Journal Article
Closed access
PDF file
JGJoachim Gudmundsson
Joachim Gudmundsson
MKMarc van Kreveld
Marc van Kreveld
BSBettina Speckmann
Bettina Speckmann


21 June 2009 in Computational Geometry
Verified
Journal Article
Closed access
PDF file
MLMaarten Löffler
Maarten Löffler
MKMarc van Kreveld
Marc van Kreveld

5 May 2012 in Algorithmica
Verified
Journal Article
Open access
PDF file
KBKevin Buchin
Kevin Buchin
MBMaike Buchin
Maike Buchin
MKMarc van Kreveld
Marc van Kreveld
MLMaarten Löffler
Maarten Löffler
RSRodrigo Silveira
Rodrigo Silveira
LWLionov Wiratma
Lionov Wiratma
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 evaluate whether the two methods yield medians that are according to our intuition. Our results suggest that the second method, using homotopy, performs considerably better.

30 June 2024 in ACM Transactions on Spatial Algorithms and Systems
Verified
Journal Article
Open access
MMMohamed Mokbel
Mohamed Mokbel
MSMahmoud Sakr
Mahmoud Sakr
LXLi Xiong
Li Xiong
AZAndreas Züfle
Andreas Züfle
JAJussara Almeida
Jussara Almeida
EZEsteban Zimanyi
Esteban Zimanyi
Mobility data captures the locations of moving objects such as humans, animals, and cars. With the availability of Global Positioning System (GPS)–equipped mobile devices and other inexpensive location-tracking technologies, mobility data is collected ubiquitously. In recent years, the use of mobility data has demonstrated a significant impact in various domains, including traffic management, urban planning, and health sciences. In this article, we present the domain of mobility data science. Towards a unified approach to mobility data science, we present a pipeline having the following components: mobility data collection, cleaning, analysis, management, and privacy. For each of these components, we explain how mobility data science differs from general data science, we survey the current state-of-the-art, and describe open challenges for the research community in the coming years.