Now showing items 1-10 of 10

    • Barbay, Jérémy (Springer Verlag, 2018)
      The discrete Fréchet distance is a measure of similarity between point sequences which permits to abstract differences of resolution between the two curves, approximating the original Fréchet distance between curves. ...
    • Barbay, Jérémy; Pérez-Lantero, Pablo; Rojas-Ledesma, Javiel (Springer Verlag, 2018)
      We consider the Minimum Coverage Kernel problem: given a set B of d-dimensional boxes, find a subset of B of minimum size covering the same region as B. This problem is NP -hard, but as for many NP -hard problems on graphs, ...
    • Barbay, Jérémy; Pérez Lantero, Pablo; Rojas Ledesma, Javiel (Elsevier, 2020)
      Given a set B of d-dimensional boxes (i.e., axis-aligned hyperrectangles), a minimum coverage kernel is a subset of B of minimum size covering the same region as B. Computing it is NP-hard, but as for many similar NP-hard ...
    • Barbay, Jérémy; Pérez Lantero, Pablo; Rojas Ledesma, Javiel (Springer, 2017)
      Motivated by the analysis of range queries in databases, we introduce the computation of the Depth Distribution of a set mathcal {B} of axis aligned boxes, whose computation generalizes that of the Klee’s Measure and of ...
    • Barbay, Jérémy; Olivares, Andrés (Springer Verlag, 2018)
      There are efficient dynamic programming solutions to the computation of the Edit Distance from S ∈in [1..σ]n to T ∈in [1..σ]m, for many natural subsets of edit operations, typically in time within O(nm) in the worst-case ...
    • Afshani, Peyman; Barbay, Jérémy; Chan, Timothy M. (ACM, 2017)
      We prove the existence of an algorithmAfor computing 2D or 3D convex hulls that is optimal forevery pointsetin the following sense: for every sequenceσofnpoints and for every algorithmA′in a certain classA,the running time ...
    • Barbay, Jérémy; Gupta, Ankur; Satti, Srinivasa Rao; Sorenson, Jon (Elsevier, 2016)
      We introduce an online version of the multiselection problem, in which q selection queries are requested on an unsorted array of nelements. We provide the first online algorithm that is 1-competitive with the offline ...
    • Barbay, Jérémy; Ochoa, Carlos (Springer Verlag, 2018)
      We describe and analyze the first adaptive algorithm for merging k convex hulls in the plane. This merging algorithm in turn yields a synergistic algorithm to compute the convex hull of a set of planar points, taking ...
    • Barbay, Jérémy; Ochoa, Carlos; Satti, Srinivasa Rao (Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017)
      Karp et al. (1988) described Deferred Data Structures for Multisets as “lazy” data structureswhich partially sort data to support online rank and select queries, with the minimum amount ofwork in the worst case over instances ...
    • Chowdhury, Avishek; Clerc, Marcel G.; Barbay, Jérémy; Robert-Philip, Isabelle; Braive, Remy (Nature, 2020)
      Driven non-linear resonators can display sharp resonances or even multistable behaviours amenable to induce strong enhancements of weak signals. Such enhancements can make use of the phenomenon of vibrational resonance, ...