Pilar Cano

dblp:41/11336 · DBLP profile ↗
← Back
8ranked-venue papers
0as first author
3since 2021 · last 2022
—ORCID · conflict

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 5 · 2 since 2021Graphics, computer vision, multimedia, augmented reality and games · 2 · 1 since 2021
YearPublicationVenuePosition
2022 Fragile complexity of adaptive algorithms
abstract
The fragile complexity of a comparison-based algorithm is $f(n)$ if each input element participates in $O(f(n))$ comparisons. In this paper, we explore the fragile complexity of algorithms adaptive to various restrictions on the input, i.e., algorithms with a fragile complexity parameterized by a quantity other than the input size~$n$. We show that searching for the predecessor in a sorted array has fragile complexity $\Theta(\log k)$, where $k$ is the rank of the query element, both in a randomized and a deterministic setting. For predecessor searches, we also show how to optimally reduce the amortized fragile complexity of the elements in the array. We also prove the following results: Selecting the $k$th smallest element has expected fragile complexity $O(\log\log k)$ for the element selected. Deterministically finding the minimum element has fragile complexity $\Theta(\log(\INV))$ and $\Theta(\log(\RUNS))$, where $\INV$ is the number of inversions in a sequence and $\RUNS$ is the number of increasing runs in a sequence. Deterministically finding the median has fragile complexity $O(\log(\RUNS) + \log\log n)$ and $\Theta(\log (\INV))$. Deterministic sorting has fragile complexity $\Theta(\log (\INV))$ but it has fragile complexity $\Theta(\log n)$ regardless of the number of runs.
Prosenjit Bose, Pilar Cano, Rolf Fagerberg, John Iacono, Riko Jacob, Stefan Langerman
Theor. Comput. Sci.2
2021 Fragile Complexity of Adaptive Algorithms
Prosenjit Bose, Pilar Cano, Rolf Fagerberg, John Iacono, Riko Jacob, Stefan Langerman
CIAC2
2021 Affine invariant triangulations
Prosenjit Bose, Pilar Cano, Rodrigo I. Silveira
Comput. Aided Geom. Des.2
2020 Flips in Higher Order Delaunay Triangulations
Elena Arseneva, Prosenjit Bose, Pilar Cano, Rodrigo I. Silveira
LATIN3
2020 Hamiltonicity for convex shape Delaunay and Gabriel graphs
Prosenjit Bose, Pilar Cano, Maria Saumell, Rodrigo I. Silveira
Comput. Geom.2
2019 Hamiltonicity for Convex Shape Delaunay and Gabriel Graphs
Prosenjit Bose, Pilar Cano, Maria Saumell, Rodrigo I. Silveira
WADS2
2018 Pole Dancing: 3D Morphs for Tree Drawings
Elena Arseneva, Prosenjit Bose, Pilar Cano, Anthony D'Angelo, Vida Dujmovic, Fabrizio Frati, Stefan Langerman, Alessandra Tappini
GD3
2010 Ambient Intelligence in Network Management
Mary Luz Mouronte-López, Pilar Cano, Miguel Angel Fernández
BROADNETS2