Akademik Veri Yönetim Sistemi
Tez Türü: Bütünleşik Doktora
Tezin Yürütüldüğü Kurum: University of California, Santa Barbara, Mühendislik Fakültesi, Bilgisayar Bilimi, Amerika Birleşik Devletleri
Tez Danışmanı: Subhash Suri
Tezin Onay Tarihi: 2014
Tezin Dili: İngilizce
Özet:
Geometric techniques are frequently utilized to analyze and reason about multidimensional
data. When confronted with large quantities of such data, simplifying geometric
statistics or summaries are often a necessary first step. In this thesis, we make
contributions to two such fundamental concepts of computational geometry: Klee’s
Measure and Convex Hulls. The former is concerned with computing the total volume
occupied by a set of overlapping rectangular boxes in d-dimensional space, while
the latter is concerned with identifying extreme vertices in a multi-dimensional set
of points. Both problems are frequently used to analyze optimal solutions to multiobjective
optimization problems: a variant of Klee’s problem called the Hypervolume
Indicator gives a quantitative measure for the quality of a discrete Pareto Optimal set,
while the Convex Hull represents the subset of solutions that are optimal with respect
to at least one linear optimization function.
In the first part of the thesis, we investigate several practical and natural variations
of Klee’s Measure Problem. We develop a specialized algorithm for a specific case of
Klee’s problem called the “grounded” case, which also solves the Hypervolume Indicator
problem faster than any earlier solution for certain dimensions. Next, we extend
Klee’s problem to an uncertainty setting where the existence of the input boxes are
defined probabilistically, and study computing the expectation of the volume. Additionally,
we develop efficient algorithms for a discrete version of the problem, where
the volume of a box is redefined to be the cardinality of its overlap with a given point
set.
The second part of the thesis investigates the convex hull problem on uncertain
input. To this extent, we examine two probabilistic uncertainty models for point sets.
The first model incorporates uncertainty in the existence of the input points. The second
model extends the first one by incorporating locational uncertainty. For both models,
we study the problem of computing the probability that a given point is contained in the
convex hull of the uncertain points. We also consider the problem of finding the most
likely convex hull, i.e., the mode of the convex hull random variable.