Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-25999
Titel: Geometric optimization and querying : exact & approximate
VerfasserIn: Matijevi, Domagoj
Sprache: Englisch
Erscheinungsjahr: 2007
Kontrollierte Schlagwörter: Geometrische Optimierung
Bühnenbeleuchtung
Voronoi-Diagramm
Datenstruktur
Abfrage
Freie Schlagwörter: WSPD
Geometric optimization
stage illumination problem
well-separated pair decomposition
Voronoi diagram
data structures
query
DDC-Sachgruppe: 004 Informatik
Dokumenttyp: Dissertation
Abstract: This thesis has two main parts. The first part deals with the stage illumination problem. Given a stage represented by a line segment L and a set of lightsources represented by a set of points S in the plane, assign powers to the lightsources such that every point on the stage receives a sufficient amount, e.g. one unit, of light while minimizing the overall power consumption. By assuming that the amount of light arriving from a fixed lightsource decreases rapidly with the distance from the lightsource, this becomes an interesting geometric optimization problem. We present different solutions, based on convex optimization, discretization and linear programming, as well as a purely combinatorial approximation algorithm. Some experimental results are also provided. In the second part of this thesis, we are concerned with two different geometric problems whose solutions are based on the construction of a data structure that would allow for efficient queries. The central idea of our data structures is the well-separated pair decomposition. The first problem we address is the k-hop restricted shortest path under the power-euclidean distance function. Given a set P of n points in the plane and the distance function jpqjd +Cp for some constant d > 1, nonnegative offset cost Cp and p;q 2 P, where jpqj denotes the Euclidean distance between p and q, we consider the problem of finding paths between any pair of points that minimize the lenght of the path and do not use more than some constant number k of hops. Known exact algorithms for this problem required W(nlogn) per query pair (p;q). We relax the exactness requirement and only require approximate (1+e) solutions which allows us to derive schemes which guarantee constant query time using linear space and O(nlogn) preprocessing time. The dependence on e is polynomial in 1=e. We also develop a tool that might be of independent interest: For any pair of points p;q 2 P report in constant time the cluster pair (A;B) representing (p;q) in a well-separated pair decomposition of P. The second problem in this part is so-called cone-restricted nearest neighbor. For a given point set in Euclidean space we consider the problem of finding (approximate) nearest neighbors of a query point but restricting only to points that lie within a fixed cone with apex at the query point. We investigate the structure of the Voronoi diagram induced by this notion of proximity and present approximate and exact data structures for answering cone-restricted nearest neighbor queries. In particular, we develop an approximate Voronoi diagram of size O((n=ed) log(1=e)) that can be used to answer cone-restricted nearest neighbor queries in O(log(n=e)) time.
Diese Arbeit besteht aus zwei Teilen. Der erste Teil behandelt das Stage Illumination Problem. Hierbei möchte man eine Bühne, die durch ein Geradenstück repräsentiert ist, durch Lichtquellen, die durch Punkte in der Ebene repräsentiert sind, so beleuchten, dass jeder Punkt der Bühne genügend Licht erhält und dabei möglichst wenig Energie verbrauchen. Wenn man annimmt, dass die Lichtintensität stark mit der Entfernung zur Lichtquelle abnimmt, so stellt dies ein interesanntes geometrisches Optimierungsproblem dar. Wir geben verschiedene Lösungen an, die sowohl auf konvexer Optimierung, Diskretisierung und Linearer Programmierung basieren, als auch einen kombinatorischen Approximationsalgorithmus. Es werden auch experimentelle Resultate angegeben. Im zweiten Teil dieser Arbeit behandeln wir zwei verschiedene geometrische Probleme, deren Lösungen auf einer Datenstruktur basieren, die effiziente Anfragen beantworten kann. Die zentrale Idee unserer Datenstruktur ist die well-separated pair decomposition WSPD. Das erste Problem, das wir ansprechen ist das k-hop restricted shortest path under the power-euclidean distance function. Für n Punkte in der Ebene möchte man den kürzesten Pfad zwischen zwei beliebigen Punkten finden, der nicht mehr als k Kanten benötigt. Bekannte exakte Algorithmen für dieses Problem benötigen W(nlogn) Zeit pro Anfrage (p;q). Wir lockern die Exaktheitsforderung und verlangen nur eine (1+e)-Approximation. Dies erlaubt uns eine Methode zu entwickeln, die konstante Zeit pro Anfrage garaniert und nur linearen Platz benötigt bei einer Vorverarbeitungszeit von O(nlogn). Die Abhängigkeit von e ist polynomiell in 1=e. Außerdem entwickeln wir eine Methode, die davon unabhängig von Interesse ist. Für ein Punktepaar p;q 2 P bestimmen wir in konstanter Zeit das Cluster-paar (A;B), das (p;q) in einer WSPD von P bestimmt. Das zweite Problem in diesem Teil ist das sogenannte cone-restricted nearest neighbor problem. Für eine gegebene Menge von Punkten im Euklidischen Raum betrachten wir das Problem den nächsten Nachbarpunkt zu bestimmen, der in einem Kegel liegt, dessen Spitze ein beliebiger Anfragepunkt ist. Wir untersuchen das dazugehörige Voronoi- Diagramm und entwickeln effiziente Datenstrukturen sowohl für exakte als auch für approximative cone-restricted nearest neighbor-Anfragen. Im speziellen entwickeln wir ein approximatives Voronoi-Diagramm der Größe O((n=ed) log(1=e)), das dazu benutzt werden kann, Anfragen in der Zeit O(log(n=e)) zu beantworten.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-32197
hdl:20.500.11880/26055
http://dx.doi.org/10.22028/D291-25999
Erstgutachter: Funke, Stefan
Tag der mündlichen Prüfung: 7-Sep-2007
Datum des Eintrags: 2-Sep-2010
Fakultät: MI - Fakultät für Mathematik und Informatik
Fachrichtung: MI - Informatik
Sammlung:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Dateien zu diesem Datensatz:
Datei Beschreibung GrößeFormat 
Dissertation_5120_Mati_Doma_2007.pdf1,32 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.