Source author record

Pilar Cano

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms

Catalog footprint

Research overview

2works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Fragile Complexity of Adaptive Algorithms

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 $Θ(\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 $Θ(\log(Inv))$ and $Θ(\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 $Θ(\log(Inv))$ . Deterministic sorting has fragile complexity $Θ(\log(Inv))$ but it has fragile complexity $Θ(\log n)$ regardless of the number of runs.

preprint2020arXiv

Compatible Paths on Labelled Point Sets

Let $P$ and $Q$ be finite point sets of the same cardinality in $\mathbb{R}^2$ , each labelled from $1$ to $n$ . Two noncrossing geometric graphs $G_P$ and $G_Q$ spanning $P$ and $Q$ , respectively, are called compatible if for every face $f$ in $G_P$ , there exists a corresponding face in $G_Q$ with the same clockwise ordering of the vertices on its boundary as in $f$ . In particular, $G_P$ and $G_Q$ must be straight-line embeddings of the same connected $n$ -vertex graph. Deciding whether two labelled point sets admit compatible geometric paths is known to be NP-complete. We give polynomial-time algorithms to find compatible paths or report that none exist in three scenarios: $O(n)$ time for points in convex position; $O(n^2)$ time for two simple polygons, where the paths are restricted to remain inside the closed polygons; and $O(n^2 \log n)$ time for points in general position if the paths are restricted to be monotone.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.