Benjamin Raichel

Benjamin Raichel

Auto-generated profile, based on publicly available information

Benjamin Raichel

Department of Computer Science University of Texas at Dallas 75080 Richardson TX USA

Research Focus & Metrics

Academic Career Length

13Years (2014-Present)

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

Representative Publications

View All Publications
19 June 2017 in Discrete & Computational Geometry
Verified
Journal Article
Closed access
PDF file
BRBenjamin Raichel
Benjamin Raichel
CSC. Seshadhri
C. Seshadhri

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.

1 August 2016 in Discrete & Computational Geometry
Verified
Journal Article
Closed access
PDF file
HCHsien-Chih Chang
Hsien-Chih Chang
SHSariel Har-Peled
Sariel Har-Peled
BRBenjamin Raichel
Benjamin Raichel

1 October 2021 in Computational Geometry
Verified
Journal Article
Closed access
GKGeorgiy Klimenko
Georgiy Klimenko
BRBenjamin Raichel
Benjamin Raichel
GBGregory Van Buskirk
Gregory Van Buskirk

3 August 2020 in Discrete & Computational Geometry
Verified
Journal Article
Closed access
PDF file
CFChenglin Fan
Chenglin Fan
BRBenjamin Raichel
Benjamin Raichel

8 June 2014
Verified
Conference Paper
Open access
PDF file
SHSariel Har-Peled
Sariel Har-Peled
BRBenjamin Raichel
Benjamin Raichel
In this paper, we provide an O(n polylog n) bound on the expected complexity of the randomly weighted Voronoi diagram of a set of n sites in the plane, where the sites can be either points, interior-disjoint convex sets, or other more general objects. Here the randomness is on the weight of the sites, not their location. This compares favorably with the worst case complexity of these diagrams, which is quadratic. As a consequence we get an alternative proof to that of Agarwal et al. [AHKS13] of the near linear complexity of the union of randomly expanded disjoint segments or convex sets (with an improved bound on the latter). The technique we develop is elegant and should be applicable to other problems.