MSc. Maria Saumell Mendiola, Ph.D.

Article

10.1016/j.tcs.2022.07.016

Department of Theoretical Computer Science

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.

Proceedings paper

10.1007/978-3-030-89543-3_22

Department of Theoretical Computer Science

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.

Proceedings paper

10.4230/LIPIcs.GIScience.2021.II.10

Department of Theoretical Computer Science

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.

Article

10.1016/j.comgeo.2020.101629

Department of Theoretical Computer Science

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.

Article

10.1016/j.ejc.2018.11.004

Department of Theoretical Computer Science

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.

Proceedings paper

10.1007/978-3-030-24766-9_15

Department of Theoretical Computer Science

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.

Article

Department of Theoretical Computer Science

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.