Shape fitting problems in the presence of outliers

• Main Author: Guo, Zhengyang
• Other Authors: -
• Format: Thesis-Doctor of Philosophy
• Language: English
• Published: Nanyang Technological University 2021
• Subjects: Science::Mathematics
• Online Access: https://hdl.handle.net/10356/148408
• Institution: Nanyang Technological University

The thesis studies three planar shape fitting problems in computational geometry, the unit square/disk cover, the minimum enclosing parallelogram and the Tukey/- convex layers. For all the three problems, we allow presence of noisy outliers, whose removal could improve the quality of the output. In convention, the covered and uncovered points are called inliers and outliers, respectively. We let n denote the size of the input point set and t the number of possible outliers. With the target to cover no less than (n − t) points of the input, we consider the minimum number of unit disks, a parallelogram of minimum area and a convex polygon of minimum area. In Chapter 3, we study the unit square/disk cover problem. Even when there is no outlier, both problems are NP-hard [57]. By extending the well-known shifting strategy [57] to the cases of outliers, we present an approximation algorithm to unit square cover, which covers at least (n − t − δt) points with at most 2 times of the optimal number of squares. We also give a (7/2, 1 + δ) bi-criteria approximation algorithm whose time complexity is O(n 7 t + δ −1ntlog n). We also introduce a restricted version of unit disk cover, where the centers of the disks are restricted to be among the input points. This restricted version is also NP-hard and we give a (1 + 6/ √ 5 + 1/`, 1 + δ) bi-criteria approximation algorithm whose runtime is O(`n4 t + δ −1 `mtlog n). Next in Chapter 4, we study the minimum enclosing parallelogram with outliers. By developing a method similar to rotating calipers [97], we can obtain all the possible positions of the parallelogram sides. Combining the different side positions, we present an exact algorithm with O |Ut+1(X)| 2 t 4 + n 2 log n runtime, with the assumption that no three points are collinear. Here Ut+1(X) denotes the first (t+1) Tukey layers of the input, consisting of the points whose Tukey depth [98] are at most (t + 1). The algorithm is quadratic in n and could be prohibitively slow for pratical use. To overcome such issue, we give a sampling algorithm with runtime O(n+poly(log n, t, 1/δ)), which with high probability finds a parallelogram covering at least (1 − δ)(n − t) points. The area of the parallelogram is no more than the optimal value. In Section 4.6, we show our exact algorithm can be adapted to the partial minimum enclosing rectangle, whose orientation can be arbitrary, improving the best known time complexity O(n 2 t 2 + n 2 tlog n) in [26] to O(n 2 t 2 + n 2 log n). In Chapter 5, we study the average case complexity of two shape fitting algorithms, both in the cases of outliers. The first is our exact algorithms for minimum enclosing parallelogram with outliers, introduced in Chapter 4. As proved in Theorem 4.12, the time complexity of the algorithm to MEPt depends on the size of the first t Tukey layers, which is denoted by |U[t](X)|. We therefore turn to study the expected size of the first t Tukey layers of the input. We show that E[U[t](X)] = O(ktlog(n/t)), when the n points are independently and uniformly sampled from a convex polygon with k vertices. Consequently, the average case complexity is O(kt5n log(n/k) + n 2 log n). In the same spirit, we also study the expected size of the first t convex layers. We show that E[V[t](X)] = O(kt3 log(n/(kt2 ))) and by this result we can compute the average case complexity of the algorithm for convex hull with outliers in [5], which is O ( n log n + k 4t2t (3t){t t3 log nkt2).