Geometric algorithms for object placement and planarity in a terrain

Abstract

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.

Wir betrachten das folgende Platzierungsproblem: Sei C eine kompakte Menge im R2 und S eine Menge von n Punkten im R2. Das Ziel ist es, ein Verschiebung von C zu berechnen, welche eine maximale Anzahl k* an Punkten aus S enthält. Aufgrund zahlreicher Anwendungen im Clustering und in der Mustererkennung wurde dieses Problem in den letzten Jahrzehnten oft betrachtet. Es gibt bekannte Algorithmen, die dieses Problem in fast-quadratischer Zeit lösen. Wir präsentieren einen Monte-Carlo Algorithmus, der für ein gegebenes epsilon > 0 in fastlinearer Zeit eine Platzierung von C berechnet, welche mindestens (1-Epsilon)k* Punkte aus S mit hoher Wahrscheinlichkeit enthält. Unser Algorithmus basiert auf der Entnahme zufälliger Stichproben und Bucketingtechniken. Im Falle, dass C eine Einheitskreisscheibe ist, stellen wir einen Approximationsalgorithmus für das Plazierungsproblem vor, wobei wir den Radius der Kreisscheibe relaxieren. So erhalten wir eine Platzierung einer Kreisscheibe mit Radius (1 + epsilon) welche mindestens k* Punkte enthält. Hierbei bezeichnet k* die maximale Anzahl von Punkten, die von einer Einheitskreisscheibe überdeckt werden können. Die Laufzeit dieses Algorithmus ist O(n/epsilon2). Danach betrachten wir das Problem, die grösste zusammenhängende Region in einem triangulierten Terrain der Grösse n zu berechnen, für welche die Dreiecksnormalen der Region um nicht mehr als einen vorgegebenen Winkel abweichen. Wir präsentieren einen exakten Algorithmus, der auf einer Datenstruktur zur dynamischen Verwaltung von Zusammenhangskomponenten eines Graphen basiert und das Problem in Lösung vor, die schnell relativ grosse planare Regionen berechnet. Diese Heuristik wurde implementiert und experimentell evaluiert. Dazu lagen uns dreidimensionale topografische Daten von Bruchoberflächen verschiedenster Metallsorten vor. Diese Anwendung war auch die ursprüngliche Motivation für unsere Forschung. Da diese Heuristik jedoch keinerlei Qualitätsgarantie für die berechnete Region liefert, stellen wir schliesslich ein neues Approximationsschema vor, welches sowohl eine garantierte Güte liefert, als auch praktisch implementiert wurde und auf unseren Testdaten gute Resultate erzielte. Die Laufzeit dieses Approximationsalgorithmus ist O(n/epsilon2).