MSc. Maria Saumell Mendiola, Ph.D.

Publikace

Minimum Color Spanning Circle in Imprecise Setup

Autoři
Acharyya, A.; Jallu, R.K.; Keikha, V.; Löffler, M.; Saumell Mendiola, M.
Rok
2021
Publikováno
27th International Computing and Combinatorics Conference (COCOON 2021). Cham: Springer, 2021. p. 257-268. vol. 13025. ISBN 978-3-030-89542-6.
Typ
Stať ve sborníku
Anotace
Let R be a set of n colored imprecise points, where each point is colored by one of k colors. Each imprecise point is specified by a unit disk in which the point lies. We study the problem of computing the smallest and the largest possible minimum color spanning circle, among all possible choices of points inside their corresponding disks. We present an O(nk*log n) time algorithm to compute a smallest minimum color spanning circle. Regarding the largest minimum color spanning circle, we show that the problem is NP-Hard and present a 1/3-factor approximation algorithm. We improve the approximation factor to 1/2 for the case where no two disks of distinct color intersect.

Terrain Prickliness: Theoretical Grounds for High Complexity Viewsheds

Autoři
Acharyya, A.; Jallu, R.K.; Löffler, M.; Meijer, G.G.T.; Saumell Mendiola, M.; Silveira, R.I.; Staals, F.
Rok
2021
Publikováno
11th International Conference on Geographic Information Science (GIScience 2021) - Part II. Wadern: Schloss Dagstuhl - Leibniz Center for Informatics, 2021. p. 10:1-10:16. LIPICS. vol. 208. ISSN 1868-8969. ISBN 978-3-95977-208-2.
Typ
Stať ve sborníku
Anotace
An important task in terrain analysis is computing viewsheds. A viewshed is the union of all the parts of the terrain that are visible from a given viewpoint or set of viewpoints. The complexity of a viewshed can vary significantly depending on the terrain topography and the viewpoint position. In this work we study a new topographic attribute, the prickliness, that measures the number of local maxima in a terrain from all possible angles of view. We show that the prickliness effectively captures the potential of terrains to have high complexity viewsheds. We present near-optimal algorithms to compute it for TIN terrains, and efficient approximate algorithms for raster DEMs. We validate the usefulness of the prickliness attribute with experiments in a large set of real terrains.

Hamiltonicity for convex shape Delaunay and Gabriel graphs

Autoři
Bose, P.; Cano, P.; Saumell Mendiola, M.; Silveira, R.
Rok
2020
Publikováno
Computational Geometry: Theory and Applications. 2020, 2020(89), ISSN 0925-7721.
Typ
Článek
Anotace
We study Hamiltonicity for some of the most general variants of Delaunay and Gabriel graphs. Instead of defining these proximity graphs using circles, we use an arbitrary convex shape $\mathcal{C}$. Let $S$ be a point set in the plane. The $k$-order Delaunay graph of $S$, denoted $k$-${DG}_{\mathcal{C}}(S)$, has vertex set $S$, and edges defined as follows. Given $p, q \in S$, $pq$ is an edge of $k$-${DG}_{\mathcal{C}}(S)$ provided there exists \emph{some} homothet of $\mathcal{C}$ with $p$ and $q$ on its boundary and containing at most $k$ points of $S$ different from $p$ and $q$. The $k$-order Gabriel graph, denoted $k$-${GG}_{\mathcal{C}}(S)$, is defined analogously, except that the homothets considered are restricted to be \emph{smallest} homothets of $\mathcal{C}$ with $p$ and $q$ on the boundary. We provide upper bounds on the minimum value of $k$ for which $k$-${GG}_{\mathcal{C}}(S)$ is Hamiltonian. Since $k$-${GG}_{\mathcal{C}}(S)$ $\subseteq$ $k$-${DG}_{\mathcal{C}}(S)$, all results carry over to $k$-${DG}_{\mathcal{C}}(S)$. In particular, we give upper bounds of 24 for every $\mathcal{C}$ and 15 for every point-symmetric $\mathcal{C}$. We also improve these bounds to 7 for squares, 11 for regular hexagons, 12 for regular octagons, and 11 for even-sided regular $t$-gons (for $t \geq 10)$. These constitute the first general results on Hamiltonicity for convex shape Delaunay and Gabriel graphs. In addition, we show lower bounds of $k=3$ and $k=6$ on the existence of a bottleneck Hamiltonian cycle in the $k$-order Gabriel graph for squares and hexagons, respectively. Finally, we construct a point set such that for an infinite family of regular polygons $\mathcal{P}_t$, the Delaunay graph ${DG}_{\mathcal{P}_t}$ does not contain a Hamiltonian cycle.

A median-type condition for graph tiling

Autoři
Piguet, D.; Saumell Mendiola, M.
Rok
2019
Publikováno
European Journal of Combinatorics. 2019, 77 90-101. ISSN 1095-9971.
Typ
Článek
Anotace
Komlós (2000) determined the asymptotically optimal minimum degree condition for covering a given proportion of vertices of a host graph by vertex-disjoint copies of a fixed graph. We show that the minimum degree condition can be relaxed in the sense that we require only a given fraction of vertices to have the prescribed degree.

Hamiltonicity for Convex Shape Delaunay and Gabriel Graphs

Autoři
Bose, P.; Cano, P.; Saumell Mendiola, M.; Silveira, R.I.
Rok
2019
Publikováno
16th International Symposium on Algorithms and Data Structures (WADS 2019). Cham: Springer, 2019. p. 196-210. vol. 11646. ISSN 0302-9743. ISBN 978-3-030-24765-2.
Typ
Stať ve sborníku
Anotace
We study Hamiltonicity for some of the most general variants of Delaunay and Gabriel graphs. Instead of defining these proximity graphs using circles, we use an arbitrary convex shape C. Let S be a point set in the plane. The k-order Delaunay graph of S, denoted k-DG_C(S), has vertex set S and edge pq provided that there exists some homothet of C with p and q on its boundary and containing at most k points of S different from p and q. The k-order Gabriel graph k-GG_C(S) is defined analogously, except for the fact that the homothets considered are restricted to be smallest homothets of C with p and q on its boundary. We provide upper bounds on the minimum value of k for which k-GG_C(S) is Hamiltonian. Since k-GG_C(S)⊆k-DG_C(S), all results carry over to k-DG_C(S). In particular, we give upper bounds of 24 for every C and 15 for every point-symmetric C. We also improve the bound to 7 for squares, 11 for regular hexagons, 12 for regular octagons, and 11 for even-sided regular t-gons (for t≥10). These constitute the first general results on Hamiltonicity for convex shape Delaunay and Gabriel graphs.

Minimal Obstructions for Partial Representations of Interval Graphs

Autoři
Klavik, P.; Saumell Mendiola, M.
Rok
2018
Publikováno
Electronic Journal of Combinatorics (E-JC),. 2018, 25(4), ISSN 1077-8926.
Typ
Článek
Anotace
Interval graphs are intersection graphs of closed intervals. A generalization of recognition called partial representation extension was introduced recently. The input gives an interval graph with a partial representation specifying some pre-drawn intervals. We ask whether the remaining intervals can be added to create an extending representation. Two linear-time algorithms are known for solving this problem. In this paper, we characterize the minimal obstructions which make partial representations non-extendible. This generalizes Lekkerkerker and Boland's characterization of the minimal forbidden induced subgraphs of interval graphs. Each minimal obstruction consists of a forbidden induced subgraph together with at most four pre-drawn intervals. A Helly-type result follows: A partial representation is extendible if and only if every quadruple of pre-drawn intervals is extendible by itself. Our characterization leads to a linear-time certifying algorithm for partial representation extension.