A faster dual algorithm for the Euclidean minimum covering ball problem

Dearing and Zeck presented a dual algorithm for the problem of the minimum covering ball in $\mathbb{R}^n$. Each iteration of their algorithm has a computational complexity of at least $\mathcal O(n^3)$. In this paper we propose a modification to their algorithm that, together with an implementation that uses updates to the QR factorization of a … Read more

A Practical Iterative Algorithm for the Art Gallery Problem using Integer Linear Programming

In the last few decades, the search for exact algorithms for known NP-hard geometric problems has intensified. Many of these solutions make use of Integer Linear Programming (ILP) modeling and rely on state of the art solvers, to be able to find optimal solutions for large instances in a matter of minutes. In this work, … Read more

The Quest for Optimal Solutions for the Art Gallery Problem: a Practical Iterative Algorithm

The general Art Gallery Problem (AGP) consists in finding the minimum number of guards sufficient to ensure the visibility coverage of an art gallery represented by a polygon. The AGP is a well known NP-hard problem and, for this reason, all algorithms proposed so far to solve it are unable to guarantee optimality except in … Read more

Optimizing the Layout of Proportional Symbol Maps: Polyhedra and Computation

Proportional symbol maps are a cartographic tool to assist in the visualization and analysis of quantitative data associated with specific locations, such as earthquake magnitudes, oil well production, and temperature at weather stations. As the name suggests, symbol sizes are proportional to the magnitude of the physical quantities that they represent. We present two novel … Read more

Locating a semi-obnoxious facility with repelling polygonal regions

In this work, a semi-obnoxious facility must be located in the Euclidean plane to give service to a group of customers. Simultaneously, a set of populated areas, with shapes approximated via polygons, must be protected from the negative effects derived from that facility. The problem is formulated as a margin maximization model, following a strategy … Read more