Samenvatting
Computational geometry is the branch of theoretical computer science that deals with
algorithms and data structures for geometric objects. The most basic geometric objects
include points, lines, polygons, and polyhedra. Computational geometry has applications
in many areas of computer science, including computer graphics, robotics, and geographic
information systems.
In many computationalgeometry problems, the theoretical worst case is achieved by input
that is in some way "unrealistic". This causes situations where the theoretical running
time is not a good predictor of the running time in practice. In addition, algorithms
must also be designed with the worstcase examples in mind, which causes them to be
needlessly complicated. In recent years, realistic input models have been proposed in an
attempt to deal with this problem. The usual form such solutions take is to limit some
geometric property of the input to a constant.
We examine a specific realistic input model in this thesis: the model where objects are
restricted to be fat. Intuitively, objects that are more like a ball are more fat, and objects
that are more like a long pole are less fat. We look at fat objects in the context of five
different problems—two related to decompositions of input objects and three problems
suggested by computer graphics.
Decompositions of geometric objects are important because they are often used as a preliminary
step in other algorithms, since many algorithms can only handle geometric objects
that are convex and preferably of low complexity. The two main issues in developing
decomposition algorithms are to keep the number of pieces produced by the decomposition
small and to compute the decomposition quickly. The main question we address is
the following: is it possible to obtain better decompositions for fat objects than for general
objects, and/or is it possible to obtain decompositions quickly? These questions are also
interesting because most research into fat objects has concerned objects that are convex.
We begin by triangulating fat polygons. The problem of triangulating polygons—that
is, partitioning them into triangles without adding any vertices—has been solved already,
but the only lineartime algorithm is so complicated that it has never been implemented.
We propose two algorithms for triangulating fat polygons in linear time that are much
simpler. They make use of the observation that a small set of guards placed at points
inside a (certain type of) fat polygon is sufficient to see the boundary of such a polygon.
We then look at decompositions of fat polyhedra in three dimensions. We show that
polyhedra can be decomposed into a linear number of convex pieces if certain fatness
restrictions aremet. We also show that if these restrictions are notmet, a quadratic number
of pieces may be needed. We also show that if we wish the output to be fat and convex,
the restrictions must be much tighter.
We then study three computationalgeometry problems inspired by computer graphics.
First, we study rayshooting amidst fat objects from two perspectives. This is the problem
of preprocessing data into a data structure that can answer which object is first hit by
a query ray in a given direction from a given point. We present a new data structure
for answering vertical rayshooting queries—that is, queries where the ray’s direction
is fixed—as well as a data structure for answering rayshooting queries for rays with
arbitrary direction. Both structures improve the best known results on these problems.
Another problem that is studied in the field of computer graphics is the depthorder problem.
We study it in the context of computational geometry. This is the problem of finding
an ordering of the objects in the scene from "top" to "bottom", where one object is above
the other if they share a point in the projection to the xyplane and the first object has a
higher zvalue at that point. We give an algorithm for finding the depth order of a group
of fat objects and an algorithm for verifying if a depth order of a group of fat objects is
correct. The latter algorithm is useful because the former can return an incorrect order if
the objects do not have a depth order (this can happen if the above/below relationship has
a cycle in it). The first algorithm improves on the results previously known for fat objects;
the second is the first algorithm for verifying depth orders of fat objects.
The final problem that we study is the hiddensurface removal problem. In this problem,
we wish to find and report the visible portions of a scene from a given viewpoint—this is
called the visibility map. The main difficulty in this problem is to find an algorithm whose
running time depends in part on the complexity of the output. For example, if all but one
of the objects in the input scene are hidden behind one large object, then our algorithm
should have a faster running time than if all of the objects are visible and have borders
that overlap. We give such an algorithm that improves on the running time of previous
algorithms for fat objects. Furthermore, our algorithm is able to handle curved objects
and situations where the objects do not have a depth order—two features missing from
most other algorithms that perform hidden surface removal.
Originele taal2  Engels 

Kwalificatie  Doctor in de Filosofie 
Toekennende instantie 

Begeleider(s)/adviseur 

Datum van toekenning  25 aug 2008 
Plaats van publicatie  Eindhoven 
Uitgever  
Gedrukte ISBN's  9789038613475 
DOI's  
Status  Gepubliceerd  2008 
Vingerafdruk Duik in de onderzoeksthema's van 'Algorithms for fat objects : decompositions and applications'. Samen vormen ze een unieke vingerafdruk.
Citeer dit
Gray, C. M. (2008). Algorithms for fat objects : decompositions and applications. Technische Universiteit Eindhoven. https://doi.org/10.6100/IR636648