Visibility Domains and Complexity
Visibility Domains and Complexity
Dokument öffnen (1MB)Art der Hochschulschrift
DissertationPrüfungsdatum
13.01.2014Datum der Veröffentlichung
05.02.2014Erstgutachter
Klein, RolfZweitgutachter
Röglin, HeikoMetadaten
Zur Langanzeige
Zitierbare Links 
Inhalt
Two problems in discrete and computational geometry are considered that are related to questions about the combinatorial complexity of arrangements of visibility domains and about the hardness of path planning under cost measures defined using visibility domains.
The first problem is to estimate the VC-dimension of visibility domains. The VC-dimension is a fundamental parameter of every range space that is typically used to derive upper bounds on the size of hitting sets. Better bounds on the VC-dimension directly translate into better bounds on the size of hitting sets. Estimating the VC-dimension of visibility domains has proven to be a hard problem.
In this thesis, new tools to tackle this problem are developed. Encircling arguments are combined with decomposition techniques of a new kind. The main ingredient of the novel approach is the idea of relativization that makes it possible to replace in the analysis of intersections the complicated visibility domains by simpler geometric ranges. The main result here is the new upper bound of 14 on the VC-dimension of visibility polygons in simple polygons that improves significantly upon the previously known best upper bound of 23. For the VC-dimension of perimeter visibility domains, the new techniques yield an upper bound of 7 that leaves only a very small gap to the best known lower bound of 5.
The second problem considered is to compute the barrier resilience of visibility domains. In barrier resilience problems, one is given a set of barriers and two points s and t in R^d. The task is to find the minimum number of barriers one has to remove such that there is a way between s and t that does not cross a barrier. In the field of sensor networks, the barriers are interpreted as sensor ranges and the barrier resilience of a network is a measure for its vulnerability.
In this thesis the very natural special case where the barriers are visibility domains is investigated. It can also be formulated in terms of finding a so-called minimum witness path.
For visibility domains in simple polygons it is shown that one can find an optimal path efficiently. For polygons with holes an approximation hardness result is shown that is stronger than previous hardness results in geometric settings. Two different three-dimensional settings are considered and their respective relations to the Minimum Neighborhood Path problem and the Minimum Color Path problem in graphs are demonstrated. For one of the three-dimensional problems a 2-approximation algorithm is designed. For the general problem of finding minimum witness paths among polyhedral obstacles it turns out that it is not approximable in a strong sense.
The first problem is to estimate the VC-dimension of visibility domains. The VC-dimension is a fundamental parameter of every range space that is typically used to derive upper bounds on the size of hitting sets. Better bounds on the VC-dimension directly translate into better bounds on the size of hitting sets. Estimating the VC-dimension of visibility domains has proven to be a hard problem.
In this thesis, new tools to tackle this problem are developed. Encircling arguments are combined with decomposition techniques of a new kind. The main ingredient of the novel approach is the idea of relativization that makes it possible to replace in the analysis of intersections the complicated visibility domains by simpler geometric ranges. The main result here is the new upper bound of 14 on the VC-dimension of visibility polygons in simple polygons that improves significantly upon the previously known best upper bound of 23. For the VC-dimension of perimeter visibility domains, the new techniques yield an upper bound of 7 that leaves only a very small gap to the best known lower bound of 5.
The second problem considered is to compute the barrier resilience of visibility domains. In barrier resilience problems, one is given a set of barriers and two points s and t in R^d. The task is to find the minimum number of barriers one has to remove such that there is a way between s and t that does not cross a barrier. In the field of sensor networks, the barriers are interpreted as sensor ranges and the barrier resilience of a network is a measure for its vulnerability.
In this thesis the very natural special case where the barriers are visibility domains is investigated. It can also be formulated in terms of finding a so-called minimum witness path.
For visibility domains in simple polygons it is shown that one can find an optimal path efficiently. For polygons with holes an approximation hardness result is shown that is stronger than previous hardness results in geometric settings. Two different three-dimensional settings are considered and their respective relations to the Minimum Neighborhood Path problem and the Minimum Color Path problem in graphs are demonstrated. For one of the three-dimensional problems a 2-approximation algorithm is designed. For the general problem of finding minimum witness paths among polyhedral obstacles it turns out that it is not approximable in a strong sense.
Schlagwörter
Algorithmische Geometrie, Diskrete Geometrie, Obere Schranke, Algorithmen, Approximation
Klassifikation (DDC)
004 InformatikGilbers, Alexander: Visibility Domains and Complexity. - Bonn, 2014. - Dissertation, Rheinische Friedrich-Wilhelms-Universität Bonn.
Online-Ausgabe in bonndoc: https://nbn-resolving.org/urn:nbn:de:hbz:5n-34931
Online-Ausgabe in bonndoc: https://nbn-resolving.org/urn:nbn:de:hbz:5n-34931
@phdthesis{handle:20.500.11811/6024,
urn: https://nbn-resolving.org/urn:nbn:de:hbz:5n-34931,
author = {{Alexander Gilbers}},
title = {Visibility Domains and Complexity},
school = {Rheinische Friedrich-Wilhelms-Universität Bonn},
year = 2014,
month = feb,
note = {Two problems in discrete and computational geometry are considered that are related to questions about the combinatorial complexity of arrangements of visibility domains and about the hardness of path planning under cost measures defined using visibility domains.
The first problem is to estimate the VC-dimension of visibility domains. The VC-dimension is a fundamental parameter of every range space that is typically used to derive upper bounds on the size of hitting sets. Better bounds on the VC-dimension directly translate into better bounds on the size of hitting sets. Estimating the VC-dimension of visibility domains has proven to be a hard problem.
In this thesis, new tools to tackle this problem are developed. Encircling arguments are combined with decomposition techniques of a new kind. The main ingredient of the novel approach is the idea of relativization that makes it possible to replace in the analysis of intersections the complicated visibility domains by simpler geometric ranges. The main result here is the new upper bound of 14 on the VC-dimension of visibility polygons in simple polygons that improves significantly upon the previously known best upper bound of 23. For the VC-dimension of perimeter visibility domains, the new techniques yield an upper bound of 7 that leaves only a very small gap to the best known lower bound of 5.
The second problem considered is to compute the barrier resilience of visibility domains. In barrier resilience problems, one is given a set of barriers and two points s and t in R^d. The task is to find the minimum number of barriers one has to remove such that there is a way between s and t that does not cross a barrier. In the field of sensor networks, the barriers are interpreted as sensor ranges and the barrier resilience of a network is a measure for its vulnerability.
In this thesis the very natural special case where the barriers are visibility domains is investigated. It can also be formulated in terms of finding a so-called minimum witness path.
For visibility domains in simple polygons it is shown that one can find an optimal path efficiently. For polygons with holes an approximation hardness result is shown that is stronger than previous hardness results in geometric settings. Two different three-dimensional settings are considered and their respective relations to the Minimum Neighborhood Path problem and the Minimum Color Path problem in graphs are demonstrated. For one of the three-dimensional problems a 2-approximation algorithm is designed. For the general problem of finding minimum witness paths among polyhedral obstacles it turns out that it is not approximable in a strong sense.},
url = {https://hdl.handle.net/20.500.11811/6024}
}
urn: https://nbn-resolving.org/urn:nbn:de:hbz:5n-34931,
author = {{Alexander Gilbers}},
title = {Visibility Domains and Complexity},
school = {Rheinische Friedrich-Wilhelms-Universität Bonn},
year = 2014,
month = feb,
note = {Two problems in discrete and computational geometry are considered that are related to questions about the combinatorial complexity of arrangements of visibility domains and about the hardness of path planning under cost measures defined using visibility domains.
The first problem is to estimate the VC-dimension of visibility domains. The VC-dimension is a fundamental parameter of every range space that is typically used to derive upper bounds on the size of hitting sets. Better bounds on the VC-dimension directly translate into better bounds on the size of hitting sets. Estimating the VC-dimension of visibility domains has proven to be a hard problem.
In this thesis, new tools to tackle this problem are developed. Encircling arguments are combined with decomposition techniques of a new kind. The main ingredient of the novel approach is the idea of relativization that makes it possible to replace in the analysis of intersections the complicated visibility domains by simpler geometric ranges. The main result here is the new upper bound of 14 on the VC-dimension of visibility polygons in simple polygons that improves significantly upon the previously known best upper bound of 23. For the VC-dimension of perimeter visibility domains, the new techniques yield an upper bound of 7 that leaves only a very small gap to the best known lower bound of 5.
The second problem considered is to compute the barrier resilience of visibility domains. In barrier resilience problems, one is given a set of barriers and two points s and t in R^d. The task is to find the minimum number of barriers one has to remove such that there is a way between s and t that does not cross a barrier. In the field of sensor networks, the barriers are interpreted as sensor ranges and the barrier resilience of a network is a measure for its vulnerability.
In this thesis the very natural special case where the barriers are visibility domains is investigated. It can also be formulated in terms of finding a so-called minimum witness path.
For visibility domains in simple polygons it is shown that one can find an optimal path efficiently. For polygons with holes an approximation hardness result is shown that is stronger than previous hardness results in geometric settings. Two different three-dimensional settings are considered and their respective relations to the Minimum Neighborhood Path problem and the Minimum Color Path problem in graphs are demonstrated. For one of the three-dimensional problems a 2-approximation algorithm is designed. For the general problem of finding minimum witness paths among polyhedral obstacles it turns out that it is not approximable in a strong sense.},
url = {https://hdl.handle.net/20.500.11811/6024}
}
Die folgenden Nutzungsbestimmungen sind mit dieser Ressource verbunden:
