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