Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/339966
Type: Artigo
Title: Solving dynamic labeling problems to optimality using solution space reductions
Author: Cano, Rafael G.
de Souza, Cid C.
de Rezende, Pedro J.
Abstract: Interactive maps are maps that allow users to execute operations that alter the state of the visualization. Two of the most common operations are rotation and scaling. As one of these operations is executed, labels must maintain their size, shape and orientation. This may cause labels that were previously disjoint to overlap. For each label, we must determine a set of active ranges (i.e., intervals of angles or scales during which the label is visible) such that no pair of overlapping labels is ever active simultaneously. The objective is to maximize the total length of the active ranges of all labels. We prove a number of properties of optimal solutions which allow us to significantly reduce the size of an integer programming formulation from the literature. These properties are independent of the particular choice of operation, which makes our reduction techniques extremely flexible. We report the results of several experiments employing operations of rotation and scaling, and using two existing benchmarks with 180 real-world instances. We obtained reductions of over 100 times in the number of variables and constraints of the formulation, which led to a decrease of up to three orders of magnitude in running times
Subject: Programação linear inteira
Country: Países Baixos
Editor: Elsevier
Rights: Fechado
Identifier DOI: 10.1016/j.tcs.2018.08.010
Address: https://www.sciencedirect.com/science/article/pii/S0304397518305267
Date Issue: 2019
Appears in Collections:IC - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
000488318900008.pdf639.46 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.