Abstract
Original language  English 

Qualification  Doctor of Philosophy 
Awarding Institution 

Supervisors/Advisors 

Award date  10 Jan 2012 
Place of Publication  Eindhoven 
Publisher  
Print ISBNs  9789038630625 
DOIs  
Publication status  Published  2012 
Fingerprint
Cite this
}
Optimal geometric data structures. / Khosravi Dehkordi, A.
Eindhoven : Technische Universiteit Eindhoven, 2012. 96 p.Research output: Thesis › Phd Thesis 1 (Research TU/e / Graduation TU/e)
TY  THES
T1  Optimal geometric data structures
AU  Khosravi Dehkordi, A.
PY  2012
Y1  2012
N2  Spatial data structures form a core ingredient of many geometric algorithms, both in theory and in practice. Many of these data structures, especially the ones used in practice, are based on partitioning the underlying space (examples are binary space partitions and decompositions of polygons) or partitioning the set of objects (examples are boundingvolume hierarchies). The efficiency of such data structuresand, hence, of the algorithms that use themdepends on certain characteristics of the partitioning. For example the performance of many algorithms that use binary space partitions (BSPs) depends on the size of the BSPs. Similarly, the performance of answering range queries using boundingvolume hierarchies (BVHs) depends on the socalled crossing number that can be associated with the partitioning on which the BVH is based. Much research has been done on the problem of computing partitioning whose characteristics are good in the worst case. In this thesis, we studied the problem from a different point of view, namely instanceoptimality. In particular, we considered the following question: given a class of geometric partitioning structureslike BSPs, simplicial partitions, polygon triangulations, …and a cost functionlike size or crossing numbercan we design an algorithm that computes a structure whose cost is optimal or close to optimal for any input instance (rather than only worstcase optimal). We studied the problem of finding optimal data structures for some of the most important spatial data structures. As an example having a set of n points and an input parameter r, It has been proved that there are input sets for which any simplicial partitions has crossing number ¿(vr). It has also been shown that for any set of n input points and the parameter r one can make a simplicial partition with stabbing number O(vr). However, there are input point sets for which one can make simplicial partition with lower stabbing number. As an example when the points are on a diagonal, one can always make a simplicial partition with stabbing number 1. We started our research by studying BSPs for line segments in the plane, where the cost function is the size of the BSPs. A popular type of BSPs for line segments are the socalled autopartitions. We proved that finding an optimal autopartition is NPhard. In fact, finding out if a set of input segments admits an autopartition without any cuts is already NPhard. We also studied the relation between two other types of BSPs, called free and restricted BSPs, and showed that the number of cuts of an optimal restricted BSP for a set of segments in R2 is at most twice the number of cuts of an optimal free BSP for that set. The details are being represented in Chapter 1 of the thesis. Then we turned our attention to socalled rectilinear rpartitions for planar point sets, with the crossing number as cost function. A rectilinear rpartition of a point set P is a partitioning of P into r subsets, each having roughly P/r points. The crossing number of the partition is defined using the bounding boxes of the subsets; in particular, it is the maximum number of bounding boxes that can be intersected by any horizontal or vertical line. We performed some theoretical as well as experimental studies on rectilinear rpartitions. On the theoretical side, we proved that computing a rectilinear rpartition with optimal stabbing number for a given set of points and parameter r is NPhard. We also proposed an exact algorithm for finding optimal rectilinear rpartitions whose running time is polynomial when r is a constant, and a faster 2approximation algorithm. Our last theoretical result showed that considering only partitions whose bounding boxes are disjoint is not sufficient for finding optimal rectilinear rpartitions. On the experimental side, we performed a comparison between four different heuristics for constructing rectilinear rpartitions. The socalled windmill KDtree gave the best results. Chapter 2 of the thesis describes all the details of our research on rectilinear rpartitions. We studied another spatial data structure in Chapter 3 of the thesis. Decomposition of the interior of polygons is one of the fundamental problems in computational geometry. In case of a simple polygon one usually wants to make a Steiner triangulation of it, and when we have a rectilinear polygon at hand, one typically wants to make a rectilinear decomposition for it. Due to this reason there are algorithms which make Steiner triangulations and rectangular decompositions with low stabbing number. These algorithms are worstcase optimal. However, similar to the two previous data structures, there are polygons for which one can make decompositions with lower stabbing numbers. In 3 we proposed a 3approximation for finding an optimal rectangular decomposition of a rectilinear polygon. We also proposed an O(1)approximation for finding optimal Steiner triangulation of a simple polygon. Finally, in Chapter 4 of the thesis, we considered another optimization problem, namely how to approximate a piecewiselinear function F: R ¿R with another piecewiselinear function with fewer pieces. Here one can distinguish two versions of the problem. The first one is called the mink problem; the goal is then to approximate the function within a given error e such that the resulting function has the minimum number of links. The second one is called the mine problem; here the goal is to find an approximation with at most k links (for a given k) such that the error is minimized. These problems have already been studied before. Our contribution is to consider the problem for socalled uncertain functions, where the value of the input function F at its vertices is given as a discrete set of different values, each with an associated probability. We show how to compute an approximation that minimizes the expected error.
AB  Spatial data structures form a core ingredient of many geometric algorithms, both in theory and in practice. Many of these data structures, especially the ones used in practice, are based on partitioning the underlying space (examples are binary space partitions and decompositions of polygons) or partitioning the set of objects (examples are boundingvolume hierarchies). The efficiency of such data structuresand, hence, of the algorithms that use themdepends on certain characteristics of the partitioning. For example the performance of many algorithms that use binary space partitions (BSPs) depends on the size of the BSPs. Similarly, the performance of answering range queries using boundingvolume hierarchies (BVHs) depends on the socalled crossing number that can be associated with the partitioning on which the BVH is based. Much research has been done on the problem of computing partitioning whose characteristics are good in the worst case. In this thesis, we studied the problem from a different point of view, namely instanceoptimality. In particular, we considered the following question: given a class of geometric partitioning structureslike BSPs, simplicial partitions, polygon triangulations, …and a cost functionlike size or crossing numbercan we design an algorithm that computes a structure whose cost is optimal or close to optimal for any input instance (rather than only worstcase optimal). We studied the problem of finding optimal data structures for some of the most important spatial data structures. As an example having a set of n points and an input parameter r, It has been proved that there are input sets for which any simplicial partitions has crossing number ¿(vr). It has also been shown that for any set of n input points and the parameter r one can make a simplicial partition with stabbing number O(vr). However, there are input point sets for which one can make simplicial partition with lower stabbing number. As an example when the points are on a diagonal, one can always make a simplicial partition with stabbing number 1. We started our research by studying BSPs for line segments in the plane, where the cost function is the size of the BSPs. A popular type of BSPs for line segments are the socalled autopartitions. We proved that finding an optimal autopartition is NPhard. In fact, finding out if a set of input segments admits an autopartition without any cuts is already NPhard. We also studied the relation between two other types of BSPs, called free and restricted BSPs, and showed that the number of cuts of an optimal restricted BSP for a set of segments in R2 is at most twice the number of cuts of an optimal free BSP for that set. The details are being represented in Chapter 1 of the thesis. Then we turned our attention to socalled rectilinear rpartitions for planar point sets, with the crossing number as cost function. A rectilinear rpartition of a point set P is a partitioning of P into r subsets, each having roughly P/r points. The crossing number of the partition is defined using the bounding boxes of the subsets; in particular, it is the maximum number of bounding boxes that can be intersected by any horizontal or vertical line. We performed some theoretical as well as experimental studies on rectilinear rpartitions. On the theoretical side, we proved that computing a rectilinear rpartition with optimal stabbing number for a given set of points and parameter r is NPhard. We also proposed an exact algorithm for finding optimal rectilinear rpartitions whose running time is polynomial when r is a constant, and a faster 2approximation algorithm. Our last theoretical result showed that considering only partitions whose bounding boxes are disjoint is not sufficient for finding optimal rectilinear rpartitions. On the experimental side, we performed a comparison between four different heuristics for constructing rectilinear rpartitions. The socalled windmill KDtree gave the best results. Chapter 2 of the thesis describes all the details of our research on rectilinear rpartitions. We studied another spatial data structure in Chapter 3 of the thesis. Decomposition of the interior of polygons is one of the fundamental problems in computational geometry. In case of a simple polygon one usually wants to make a Steiner triangulation of it, and when we have a rectilinear polygon at hand, one typically wants to make a rectilinear decomposition for it. Due to this reason there are algorithms which make Steiner triangulations and rectangular decompositions with low stabbing number. These algorithms are worstcase optimal. However, similar to the two previous data structures, there are polygons for which one can make decompositions with lower stabbing numbers. In 3 we proposed a 3approximation for finding an optimal rectangular decomposition of a rectilinear polygon. We also proposed an O(1)approximation for finding optimal Steiner triangulation of a simple polygon. Finally, in Chapter 4 of the thesis, we considered another optimization problem, namely how to approximate a piecewiselinear function F: R ¿R with another piecewiselinear function with fewer pieces. Here one can distinguish two versions of the problem. The first one is called the mink problem; the goal is then to approximate the function within a given error e such that the resulting function has the minimum number of links. The second one is called the mine problem; here the goal is to find an approximation with at most k links (for a given k) such that the error is minimized. These problems have already been studied before. Our contribution is to consider the problem for socalled uncertain functions, where the value of the input function F at its vertices is given as a discrete set of different values, each with an associated probability. We show how to compute an approximation that minimizes the expected error.
U2  10.6100/IR721255
DO  10.6100/IR721255
M3  Phd Thesis 1 (Research TU/e / Graduation TU/e)
SN  9789038630625
PB  Technische Universiteit Eindhoven
CY  Eindhoven
ER 