Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/305630
Type: TESE DIGITAL
Degree Level: Doutorado
Title: Finding geometric structures with minimum stabbing number = Encontrando estruturas geométricas com número de trespasse mínimo
Title Alternative: Encontrando estruturas geométricas com número de trespasse mínimo
Author: Piva, Breno, 1983-
Advisor: Souza, Cid Carvalho de, 1963-
Abstract: Resumo: Problemas de trespasse têm sido investigados há tempos em Geometria Computacional pois aplicações para eles são encontradas em uma grande variedade de áreas. Em geral, a entrada é formada por dois conjuntos de objetos geométricos: o conjunto, finito ou infinito, L de trespassadores e o conjunto O. Uma solução viável é um subconjunto O' de O satisfazendo uma certa propriedade estrutural $\pi$. Dado O', o número de trespasse de l em L é a quantidade de elementos de O' intersectados por l. O número de trespasse de O' relativo a L é o número de trespasse máximo dentre qualquer l em L. O objetivo do problema é achar um subconjunto de O satisfazendo a propriedade $\pi$ com o menor número de trespasse possível relativo a L. Esta tese traz contribuições tanto teóricas quanto experimentais para alguns problemas de trespasse. Em [19, 20], Fekete, Lübbecke e Meijer resolveram o problema aberto a respeito da complexidade de encontrar uma árvore geradora com número de trespasse mínimo. Eles também mostraram que achar um emparelhamento perfeito com número de trespasse mínimo é NP-difícil. Modelos de programação inteira para os problemas foram apresentados. Porém, muito poucos experimentos computacionais foram realizados. Nesta tese, estudamos modelos de programação inteira para encontrar emparelhamentos perfeitos, árvores geradoras e triangulação com número de trespasse mínimo. Com base nestas formulações, apresentamos algoritmos exatos e heurísticas Lagrangianas para resolvê-los. Estes algoritmos mostraram que as heurísticas Lagrangianas proveem boas soluções, frequentemente ótimas, em um breve tempo computacional. De todos os dez problemas e variantes discutidos em [20], para apenas três deles a complexidade não foi provada: Triangulação com Número de Trespasse Mínimo, com trespassadores paralelos aos eixos e gerais, e Triangulação com Número de Cruzamento Mínimo, caso geral. Nesta tese, provamos que estes três problemas são NP-difíceis. Outro problema de trespasse mínimo é apresentado em [2] e também estudado em [16]. Este problema pede por uma partição retangular com número de trespasse mínimo em um polígono retilinear. Embora a complexidade do problema ainda seja desconhecida, em [2] um algoritmo de 3-aproximação é apresentado. Em [16] um modelo de programação inteira é dado e uma 2-aproximação reivindicada. Nesta tese, fortalecemos a formulação introduzida em [16]. Também propomos um modelo alternativo e comparamos os dois teórica e computacionalmente. Além disso, mostramos que o algoritmo proposto em [16] não provê uma 2-aproximação para o problema

Abstract: Stabbing problems have long being investigated in Computational Geometry since applications for them are found in a great variety of areas. In general, the input is formed by two sets of geometrical objects: the finite or infinite set L of stabbers and the set O. A feasible solution for the problem is a subset O' of O satisfying a given structural property $\pi$. Given O', the stabbing number of l in L is the total of elements of O' that are intersected by l. The stabbing number of L relative to O' is the maximum stabbing number of all its elements. The goal of the problem is to find a subset of O satisfying property $\pi$ and having the smallest possible stabbing number. This thesis brings both theoretical and experimental contributions to the investigation of some stabbing problems. The works of Fekete, Lübbecke and Meijer [19, 20] solved the open problem relative to the complexity of finding a spanning tree with minimum stabbing number. They also showed that finding a perfect matching with minimum stabbing number is NP-hard. Integer programming formulations for the problems were also presented. However, very few computational experiments were performed. In this thesis we study integer programming formulations for the problems of finding perfect matchings, spanning trees and triangulations with minimum stabbing number. Based on these formulations we present exact algorithms and Lagrangian heuristics to solve the problems. These algorithms show that the Lagrangian heuristics yield solutions with good quality, often optimal, in short time span. Of all the ten problems and variants discussed in [20], for only three of them the complexity was not proved: The Minimum Stabbing Triangulation, axis-parallel and general cases, and The Minimum Crossing Triangulation, general case. In this thesis we prove that the three problems are NP-hard. Another problem of finding a structure with minimum stabbing number is presented in [2] and also studied in [16]. This problem asks for a rectangular partition with minimum stabbing number in a rectilinear polygon. Although the complexity of the problem is still unkown, in [2] a 3-approximation algorithm is presented. In [16] an integer programming formulation is given and a 2-approximation is claimed. In this thesis we strengthen the formulation introduced in [16]. We also propose an alternative model and compare the formulations both theoretically and computationally. Furthermore, we show that the algorithm proposed in [16] can not provide a 2-approximation for the problem
Subject: Otimização combinatória
Geometria computacional
Complexidade computacional
Programação inteira
Language: Inglês
Editor: [s.n.]
Date Issue: 2016
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Piva_Breno_D.pdf1.59 MBAdobe PDFView/Open


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