Aleksandr Popov

Aleksandr Popov

Auto-generated profile, based on publicly available information

Aleksandr Popov

TU Eindhoven, The Netherlands

Research Focus & Metrics

Academic Career Length

7Years (2020-Present)

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

Representative Publications

View All Publications
11 August 2022 in Computational Geometry
Verified
Journal Article
Open access
KBKevin Buchin
Kevin Buchin
MLMaarten Löffler
Maarten Löffler
TOTim Ophelders
Tim Ophelders
APAleksandr Popov
Aleksandr Popov
JUJérôme Urhausen
Jérôme Urhausen
KVKevin Verbeek
Kevin Verbeek

14 July 2023 in ACM Transactions on Algorithms
Verified
Journal Article
Open access
KBKevin Buchin
Kevin Buchin
CFChenglin Fan
Chenglin Fan
MLMaarten Löffler
Maarten Löffler
APAleksandr Popov
Aleksandr Popov
BRBenjamin Raichel
Benjamin Raichel
MRMarcel Roeloffzen
Marcel Roeloffzen
In this article, we study a wide range of variants for computing the (discrete and continuous) Fréchet distance between uncertain curves. An uncertain curve is a sequence of uncertainty regions, where each region is a disk, a line segment, or a set of points. A realisation of a curve is a polyline connecting one point from each region. Given an uncertain curve and a second (certain or uncertain) curve, we seek to compute the lower and upper bound Fréchet distance, which are the minimum and maximum Fréchet distance for any realisations of the curves. We prove that both problems are NP-hard for the Fréchet distance in several uncertainty models, and that the upper bound problem remains hard for the discrete Fréchet distance. In contrast, the lower bound (discrete [ 5 ] and continuous) Fréchet distance can be computed in polynomial time in some models. Furthermore, we show that computing the expected (discrete and continuous) Fréchet distance is #P-hard in some models. On the positive side, we present an FPTAS in constant dimension for the lower bound problem when Δ/δ is polynomially bounded, where δ is the Fréchet distance and Δ bounds the diameter of the regions. We also show a near-linear-time 3-approximation for the decision problem on roughly δ-separated convex regions. Finally, we study the setting with Sakoe–Chiba time bands, where we restrict the alignment between the curves, and give polynomial-time algorithms for the upper bound and expected discrete and continuous Fréchet distance for uncertainty modelled as point sets.

31 July 2021
Verified
Book Chapter
Closed access
PDF file
KBKevin Buchin
Kevin Buchin
MLMaarten Löffler
Maarten Löffler
TOTim Ophelders
Tim Ophelders
APAleksandr Popov
Aleksandr Popov
JUJérôme Urhausen
Jérôme Urhausen
KVKevin Verbeek
Kevin Verbeek

24 April 2020 in arXiv
Verified
Preprint
Open access
PDF file
KBKevin Buchin
Kevin Buchin
CFChenglin Fan
Chenglin Fan
MLMaarten Löffler
Maarten Löffler
APAleksandr Popov
Aleksandr Popov
BRBenjamin Raichel
Benjamin Raichel
MRMarcel Roeloffzen
Marcel Roeloffzen
In this paper we study a wide range of variants for computing the (discrete and continuous) Fr\'echet distance between uncertain curves. We define an uncertain curve as a sequence of uncertainty regions, where each region is a disk, a line segment, or a set of points. A realisation of a curve is a polyline connecting one point from each region. Given an uncertain curve and a second (certain or uncertain) curve, we seek to compute the lower and upper bound Fr\'echet distance, which are the minimum and maximum Fr\'echet distance for any realisations of the curves. We prove that both the upper and lower bound problems are NP-hard for the continuous Fr\'echet distance in several uncertainty models, and that the upper bound problem remains hard for the discrete Fr\'echet distance. In contrast, the lower bound (discrete and continuous) Fr\'echet distance can be computed in polynomial time. Furthermore, we show that computing the expected discrete Fr\'echet distance is #P-hard when the uncertainty regions are modelled as point sets or line segments. The construction also extends to show #P-hardness for computing the continuous Fr\'echet distance when regions are modelled as point sets. On the positive side, we argue that in any constant dimension there is a FPTAS for the lower bound problem when $\Delta / \delta$ is polynomially bounded, where $\delta$ is the Fr\'echet distance and $\Delta$ bounds the diameter of the regions. We then argue there is a near-linear-time 3-approximation for the decision problem when the regions are convex and roughly $\delta$-separated. Finally, we also study the setting with Sakoe--Chiba time bands, where we restrict the alignment between the two curves, and give polynomial-time algorithms for upper bound and expected discrete and continuous Fr\'echet distance for uncertainty regions modelled as point sets.