11 citations · 41 across the 16 of their papers we have counts for
14 papers · 1 filter
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…
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…
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…
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…
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…