11 citations · 41 across the 16 of their papers we have counts for
18 papers
On Reconstructing a Convex Polygon from Partial Information
Alexander Baumann, Therese Biedl, Mahmoud Elashmawi +3
The reconstruction problem asks to construct a (convex) polygon that has a specified set of features, such as an ordered set of edge-lengths or an ordered set of polygon-angles. In…
Computing largest minimum color-spanning intervals of imprecise points
Ankush Acharyya, Vahideh Keikha, Maria Saumell +1
We study a geometric facility location problem under imprecision. Given unit intervals in the real line, each with one of colors, the goal is to place one point in each int…
On Voronoi visibility maps of 1.5D terrains with multiple viewpoints
Vahideh Keikha, Maria Saumell
Given an -vertex 1.5D terrain $\T$ and a set $\A$ of viewpoints, the Voronoi visibility map $\vorvis(\T,\A)$ is a partitioning of $\T$ into regions such that each region i…
Minimum color spanning circle of imprecise points
Ankush Acharyya, Ramesh K. Jallu, Vahideh Keikha +2
Let be a set of colored imprecise points, where each point is colored by one of colors. Each imprecise point is specified by a unit disk in which the point lies. W…
Terrain prickliness: theoretical grounds for high complexity viewsheds
Ankush Acharyya, Maarten Löffler, Gert G. T. Meijer +3
An important task in terrain analysis is computing \emph{viewsheds}. A viewshed is the union of all the parts of the terrain that are visible from a given viewpoint or set of viewp…
A median-type condition for graph tiling
Diana Piguet, Maria Saumell
Komlos [Tiling Turan theorems, Combinatorica, 20,2 (2000), 203{218] determined the asymptotically optimal minimum degree condition for covering a given proportion of vertices of a…
Colored ray configurations
Ruy Fabila-Monroy, Alfredo García, Ferran Hurtado +6
We study the cyclic color sequences induced at infinity by colored rays with apices being a given balanced finite bichromatic point set. We first study the case in which the rays a…
Geometric Biplane Graphs II: Graph Augmentation
Alfredo García, Ferran Hurtado, Matias Korman +5
We study biplane graphs drawn on a finite point set in the plane in general position. This is the family of geometric graphs whose vertex set is and which can be decomposed…
Geometric Biplane Graphs I: Maximal Graphs
Alfredo García, Ferran Hurtado, Matias Korman +5
We study biplane graphs drawn on a finite planar point set in general position. This is the family of geometric graphs whose vertex set is and can be decomposed into two pl…
The Dual Diameter of Triangulations
Matias Korman, Stefan Langerman, Wolfgang Mulzer +3
Let $\Poly$ be a simple polygon with vertices. The \emph{dual graph} $\triang^*$ of a triangulation~$\triang$ of~$\Poly$ is the graph whose vertices correspond to the bounded f…
10-Gabriel graphs are Hamiltonian
Tomáš Kaiser, Maria Saumell, Nico Van Cleemput
Given a set of points in the plane, the -Gabriel graph of is the geometric graph with vertex set , where are connected by an edge if and only if the cl…
Minimal Obstructions for Partial Representations of Interval Graphs
Pavel Klavík, Maria Saumell
Interval graphs are intersection graphs of closed intervals. A generalization of recognition called partial representation extension was introduced recently. The input gives an int…
Peeling potatoes near-optimally in near-linear time
Sergio Cabello, Josef Cibulka, Jan Kynčl +2
We consider the following geometric optimization problem: find a convex polygon of maximum area contained in a given simple polygon with vertices. We give a randomized near…
Flips in combinatorial pointed pseudo-triangulations with face degree at most four
Oswin Aichholzer, Thomas Hackl, David Orden +3
In this paper we consider the flip operation for combinatorial pointed pseudo-triangulations where faces have size 3 or 4, so-called combinatorial 4-PPTs. We show that every combin…
Terrain visibility with multiple viewpoints
Ferran Hurtado, Maarten Löffler, Inês Matos +4
We study the problem of visibility in polyhedral terrains in the presence of multiple viewpoints. We consider a triangulated terrain with viewpoints (or guards) located on th…
Extending Partial Representations of Proper and Unit Interval Graphs
Pavel Klavík, Jan Kratochvíl, Yota Otachi +4
The recently introduced problem of extending partial interval representations asks, for an interval graph with some intervals pre-drawn by the input, whether the partial representa…
Making triangulations 4-connected using flips
Prosenjit Bose, Dana Jansens, André van Renssen +2
We show that any combinatorial triangulation on n vertices can be transformed into a 4-connected one using at most floor((3n - 9)/5) edge flips. We also give an example of an infin…
On the Number of Higher Order Delaunay Triangulations
Dieter Mitsche, Maria Saumell, Rodrigo I. Silveira
Higher order Delaunay triangulations are a generalization of the Delaunay triangulation which provides a class of well-shaped triangulations, over which extra criteria can be optim…