International Journal of Computational Geometry & Applications

Many applications like image processing, data compression or pattern recognition require a covering of a set of n points most often located in the (discrete) plane by rectangles due to specific cost constraints. In this paper we provide exact dynamic programming algorithms for covering point sets by regular rectangles, that have to obey certain boundary conditions, namely all rectangles must have lengths of at least k, which is a prescribed problem parameter. The concrete objective function underlying our optimization problem is the sum of area, circumference and a constant over all rectangles forming a covering. This objective function can be motivated by requirements of numerically solving PDE's by discretization over (adaptive multi-)grids.

More precisely, we propose exact deterministic algorithms for such problems based on a (set theoretic) dynamic programming approach yielding a time bound of O(n²3ⁿ). In a second step this bound is (asymptotically) decreased to O(n⁶2ⁿ) by exploiting some structural features. Finally, a generalization of the problem and its solution methods is discussed for the case of arbitrary (finite) space dimension.

Driven by the industrial challenge of labeling maps for GIS applications, we investigate the problem of computing a map region P such that a rectangular axis-parallel label L of a given size can be placed in it. The map region to be labeled is in general a non-convex n-gon which may contain holes. We first derive a new practical algorithm based on the sweep-line technique that determines the com set of Maximum Inscribed Rectangles (MIRs) in P in O(nk), where k is the size of the output, for the case when the polygon sides have an axis-parallel orientation. After the set of MIRs has been found, any subsequent query on label L placement runs in only O(logn) time. We then provide an algorithm to convert the general case to the axis-parallel case. Extensive experimentation in both laboratory and industrial settings confirms that the developed method is practical and highly efficient for processing large GIS data sets.

Two points a and b are said to be L-visible among a set of polygonal obstacles if the length of the shortest path from a to b avoiding these obstacles is no more than L. For a given convex polygon P with n vertices, Gewali et al.¹ addressed the guard placement problem on the boundary of P that covers the maximum area outside to the polygon under L-visibility with P as obstacle. Their proposed algorithm runs in O(n) time if , where π(P) denotes the perimeter of P. They conjectured that if , then the problem can be solved in subquadratic time. In this paper, we settle the conjecture in the affirmative sense, by proposing an easy to implement linear time algorithm for any arbitrary value of L.

It has been suggested in the literature that ordinary finite-precision floating-point arithmetic is inadequate for geometric computation, and that researchers in numerical analysis may believe that the difficulties of error in geometric computation can be overcome by simple approaches. It is the purpose of this paper to show that these suggestions, based on an example showing failure of a certain algorithm for computing planar convex hulls, are misleading, and why this is so.

It is first shown how the now-classical backward error analysis can be applied in the area of computational geometry. This analysis is relevant in the context of uncertain data, which may well be the practical context for computational-geometry algorithms such as, say, those for computing convex hulls. The exposition will illustrate the fact that the backward error analysis does not pretend to overcome the problem of finite precision: it merely provides a way to distinguish those algorithms that overcome the problem to whatever extent it is possible to do so.

It is then shown that often the situation in computational geometry is exactly parallel to other areas, such as the numerical solution of linear equations, or the algebraic eigenvalue problem. Indeed, the example mentioned can be viewed simply as an example of the use of an unstable algorithm, for a problem for which computational geometry has already discovered provably stable algorithms.

Finally, the paper discusses the implications of these analyses for applications in three-dimensional solid modeling. This is done by considering a problem defined in terms of a simple extension of the planar convex-hull algorithm, namely, the verification of the well-formedness of extruded objects. A brief discussion concerning more difficult problems in solid modeling is also included.