Dilation, Transport, Visibility and Fault-Tolerant Algorithms

Abstract

Connecting some points in the plane by a road network is equivalent to constructing a <i>finite</i> planar graph <i>G</i> whose vertex set contains a predefined set of vertices (i. e., the possible destinations in the road network). The <i>dilation</i> between two vertices <i>p</i> and <i>q</i> of graph <i>G</i> is defined as the Euclidean length of a shortest path in <i>G</i> from <i>p</i> to <i>q</i>, divided by the Euclidean distance from <i>p</i> to <i>q</i>. That is, given a point set <i>P</i>, the goal is to place some additional <i>crossing vertices</i> <i>C</i> such that there exists a planar graph <i>G</i> = (<i>P</i> ∪ <i>C, E</i>) whose dilation is small. Here, the dilation of <i>G</i> is defined as the maximum dilation between two vertices in <i>G</i>. We show that, except for some special point sets <i>P</i>, there is a lower bound Δ(<i>P</i>) > 1, depending on <i>P</i>, on the dilation of any finite graph containing <i>P</i> in its vertex set. <br /> The transportation problem is the problem of finding a transportation plan that minimizes the total transport cost. We are given a set of suppliers, and each supplier produces a fixed amount of some commodity, say, bread. Furthermore, there is a set of customers, and each customer has some demand of bread, such that the total demand equals the amount of bread the suppliers produce. The task is to assign each unit of bread produced to some customer, such that the total transportation cost becomes a minimum. A first idea is to assign each unit of bread to the client to which the transport cost of this unit is minimal. Clearly, this gives rise to a transportation plan which minimizes the total transportation cost. However, it is likely that not every customer will obtain the required amount of bread. Therefore, we need to use a different algorithm for distributing the supplier's bread. We show that if the bread produced by the suppliers is given by a continuous probability density function and the set of customers is discrete, then every optimal transport plan can be characterized by a unique additively weighted Voronoi diagram for the customers. <br /> When managing the construction process of a building by a digital model of the building, it is necessary to compute <i>essential</i> parts between walls of the building. Given two walls <i>A</i> and <i>B</i>, the essential part between <i>A</i> and <i>B</i> is the set of line segments <i>s</i> where one endpoint belongs to <i>A</i>, the other endpoint belongs to <i>B</i>, and <i>s</i> does not intersect <i>A</i> or <i>B</i>. We give an algorithm that computes, in linear time, the essential parts between <i>A</i> and <i>B</i>. Our algorithm is based on computing the visibility polygon of <i>A</i> and of <i>B</i>, and two shortest paths connecting points of <i>A</i> with points of <i>B</i>. <br /> We conclude the thesis by giving fault-tolerant algorithms for some fundamental geometric problems. We assume that a basic primitive operation used by an algorithm fails with some small probability <i>p</i>. Depending on the results of the primitive operations, it is possible that the algorithm will not work correctly. For example, one faulty comparison when executing a sorting algorithm can result in some numbers being placed far away from their true positions. An algorithm is called <i>tolerant</i>, if with high probability a good answer is given, if the error probability <i>p</i> is small. We provide tolerant algorithms that find the maximum of <i>n</i> numbers, search for a key in a sorted sequence of <i>n</i> keys, sort a set of <i>n</i> numbers, and solve Linear Programming in R².