We consider the following placement problem: Let C be a compact set in R2 and let S be a set of n points in R2. The objective is to compute a translate of C that contains the maximum number, kappa*, of points of S. Motivated by the applications in clustering and pattern recognition, this optimal placement problem has received much attention over the last two decades. It is known that this problem can be solved in a time that is roughly quadratic in n. We show for a given epsilon > 0 how random-sampling and bucketing techniques can be used to develop a near-linear-time Monte Carlo algorithm that computes a placement of C containing at least (1 -epsilon)k* points of S with high probability. When C is a unit disk, we give an approximation algorithm for the optimal placement problem by approximating the constraining radius of the disk. Here, our algorithm computes a placement of the disk of radius (1 + epsilon)which contains at least k* points, where k* denotes the maximum number of points covered by any unit disk. the running time of this algorithm is O(n/epsilon2) Then, we turn to the problem of computing the largest connected region in a triangulated terrain of size n for which the normals of the triangles deviate by at most some small fixed angle. we devise an exact algorithm by adapting dynamic graph connectivity algorithm to compute the largest planar region in O(n2log n(log logn)3) time. We also give a heuristic that can be used to compute sufficiently large planar regions in a terrain much faster. We discuss an implementation of this heurisitc, and show some experimental results for terrains representing three-dimensional (topographical) images of fracture surfaces of metals obtained by confocal laser scanning microscopy, which directly motivated our research into this direction. Since the output of this heuristic comes with no quality assurance, we present a new approximation scheme for the same problem wich apart from giving a guarantee on the quality of the produced solution also has been implemented in practice and shows good performance on real-worls data representing fracture surfaces. This approximate deterministic algorithm computes in O(n/epsilon2) time the largest approximately connected planar region in the terrain. We also give a variant of the above algorithm with a better dependence on epsilon at the cost of an extra poly-logarithmic facto on n. For a sufficiently large n, both the algorithms consume optimal O(n) space.
展开▼
