Abstract
The problem of simplifying a planar subdivision has a broad range of applications, in areas such as geographic information systems (GIS), image processing, VLSI design and data compression. A well-known problem is to compute a simplification using the minimum number of segments, while ensuring that every point of the simplification is within some specified error distance to the original subdivision. This problem is usually called the min-# problem. In this thesis, we consider three separate vertex-selection criteria (models) for the simplification: (1) using only the vertices of the input subdivision, (2) using any point on the edges of the input, (3) using any points in the plane. We consider two categories of problems by applying these criteria to rectilinear and general subdivisions, respectively. First we show that the three variants for simplifying rectilinear subdivisions are all NP-complete. In the proofs, only monotone polylines with a constant number of segments are used in the construction. We further show that the three variants for simplifying general subdivisions are also all NP-complete. In the proofs, only monotone polylines with at most four segments are used. Two of these three proofs largely simplify the previously known NP-complete proofs for the corresponding problems. We obtain a unified proof framework to prove the above six NP-hardness by reducing from planar monotone 3SAT to the corresponding problems. Apart from these NP-completeness proofs, we propose several optimal algorithms for simplifying rectilinear planar subdivisions. For a constant number k of rectilinear or general x- monotone polylines, we present an O(kn^(4k+1))-time algorithm to solve the simplification problems for criterion (1), and an O(kn^(6k+1))-time algorithm for criteria (2) and (3).