Browsing by Author "8cc8cb5d-d130-4edb-aaa0-76f27e41f320"

Now showing items 1-10 of 10

    • Adaptive computation of the discrete Fréchet distance 
      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. ...
    • Computing coverage kernels under restricted settings 
      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, ...
    • Computing coverage kernels under restricted settings 
      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 ...
    • Depth distribution in high dimensions 
      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 ...
    • Indexed dynamic programming to boost edit distance and LCSS computation 
      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 ...
    • Instance-optimal geometric algorithms 
      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 ...
    • Near-optimal online multiselection in internal and external memory 
      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 ...
    • Synergistic solutions for merging and computing planar convex hulls 
      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 ...
    • Synergistic solutions on multisets 
      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 ...
    • Weak signal enhancement by nonlinear resonance control in a forced nano-electromechanical resonator 
      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, ...