Tübingen, Univ., Diss., 2002.

To make computations on large data sets more efficient, algorithms will frequently divide information into smaller, more manageable, pieces. This idea, for example, forms the basis of the common algorithmic approach known as Divide and Conquer. If we wish to use this principle in planar geometric computations, however, we may require specialized techniques for decomposing our data. This is due to the fact that the data sets are typically points, lines, regions, or polygons. This motivates algorithms that can break-up polygons into simpler pieces. Algorithms that perform such computations are said to compute polygon decompositions. There are many ways that we can decompose a polygon, and there are also many types of polygons that we could decompose. Both applications and theoretical interest demand algorithms for a wide variety of decomposition problems. In this thesis we study two different polygon decomposition problems. The first problem that we study is a polygon decomposition problem that is equivalent to the Rectilinear Art Gallery problem. In this problem we seek a decomposition of a polygon into so-called r-stars. These r-stars model visibility in an orthogonal setting. We show that we can compute a certain type of decomposition, known as a Steinercover, of a simple orthogonal polygon into r-stars in polynomial time. In the second problem, we explore the complexity of decomposing polygons into components that have an upper bound on their size. In this problem, the size of a polygon refers to the size of its bounding-box. This problem is motivated by a polygon collision detection heuristic that approximates a polygon by its bounding-box to determine whether an exact collision detection computation should take place. We show that it is NP-complete to decide whether a polygon that contains holes can be decomposed into a specified number of size-constrained components.

To make computations on large data sets more efficient, algorithms will frequently divide information into smaller, more manageable, pieces. This idea, for example, forms the basis of the common algorithmic approach known as Divide and Conquer. If we wish to use this principle in planar geometric computations, however, we may require specialized techniques for decomposing our data. This is due to the fact that the data sets are typically points, lines, regions, or polygons. This motivates algorithms that can break-up polygons into simpler pieces. Algorithms that perform such computations are said to compute polygon decompositions. There are many ways that we can decompose a polygon, and there are also many types of polygons that we could decompose. Both applications and theoretical interest demand algorithms for a wide variety of decomposition problems. In this thesis we study two different polygon decomposition problems. The first problem that we study is a polygon decomposition problem that is equivalent to the Rectilinear Art Gallery problem. In this problem we seek a decomposition of a polygon into so-called r-stars. These r-stars model visibility in an orthogonal setting. We show that we can compute a certain type of decomposition, known as a Steinercover, of a simple orthogonal polygon into r-stars in polynomial time. In the second problem, we explore the complexity of decomposing polygons into components that have an upper bound on their size. In this problem, the size of a polygon refers to the size of its bounding-box. This problem is motivated by a polygon collision detection heuristic that approximates a polygon by its bounding-box to determine whether an exact collision detection computation should take place. We show that it is NP-complete to decide whether a polygon that contains holes can be decomposed into a specified number of size-constrained components.

In this thesis, we discuss a new kind of polygon, which we call one-sided polygons. The shortest path between any pair of vertices of a one-sided polygon makes only left turns or right turns. We prove that the set of one-sided polygons is a superset of the star-shaped polygons and the spiral polygons. We also show that the set of one-sided polygons is a subset of the set of LR-visibility polygons. We present a linear time recognition algorithm for one-sided rectilinear polygons. We then discuss the searching of monotone and one-sided rectilinear polygons. We show that all one-sided polygons can be 1-searched and a search schedule can be given in linear time.

In this thesis, we discuss a new kind of polygon, which we call one-sided polygons. The shortest path between any pair of vertices of a one-sided polygon makes only left turns or right turns. We prove that the set of one-sided polygons is a superset of the star-shaped polygons and the spiral polygons. We also show that the set of one-sided polygons is a subset of the set of LR-visibility polygons. We present a linear time recognition algorithm for one-sided rectilinear polygons. We then discuss the searching of monotone and one-sided rectilinear polygons. We show that all one-sided polygons can be 1-searched and a search schedule can be given in linear time.

Every (convex) star polygon with n vertices can be associated with a permutation on {1,2, . . . , n } . It is known that the sum of interior angles of the polygon is solely determined by £». In this thesis, we give an exact formula to calculate the sum of interior angles in term of £». We make use of this formula to derive a recurrence relation concerning the number of star polygons having a particular value of sums of interior angles.

<p>When two distributed parties want to share information stored in ontologies, they have to make sure that they refer to the same concepts. This is done matching the ontologies.</p><p>This thesis will show the implementation of a method for automatic ontology matching based on the representation of polygons. The method is used to compare two ontologies and determine the degree of similarity between them.</p><p>The first of the ontologies will be taken as the standard, while the other will be compared to it by analyzing the elements in both. According to the degrees of similarity obtained from the comparison of elements, a set of polygons is represented for the standard ontology and another one for the second ontology.</p><p>Comparing the polygons we obtain the final result of the similarity between the ontologies.</p><p>With that result it is possible to determine if two ontologies handle information referred to the same concept.</p>

No description available.

Techn. Universiẗat, Diss.--Berlin, 1998.

University, Diss., 2004--Bonn. / Erscheinungsjahr auf der Hauptitelstelle: 2003.