{"id":{"repo_id":"fu-berlin","oai_identifier":"oai:refubium.fu-berlin.de:fub188/12114"},"canonical_url":"https://search.dev.ndltd.org/etd/fu-berlin/oai:refubium.fu-berlin.de:fub188/12114","repository":{"repo_id":"fu-berlin","name":"Freie Universität Berlin","base_url":"https://refubium.fu-berlin.de/oai/request"},"display":{"title":"Algorithmen zum Vergleich geometrischer Muster","abstract":"Das geometrische Mustererkennungsproblem besteht darin, zu zwei gegebenen Mustern P und Q aus einer Menge von zulässigen Mustern Π und einem Abstandsmaß δ für solche Muster eine Transformation τ aus einer Menge von zulässigen Transformationen T zu finden, so daß der Abstand δ(τ(P),Q) möglichst klein wird. In der Dissertation werden effiziente Algorithmen für verschiedenen Varianten dieser Problemstellung vorgestellt; die Ergebnisse lassen sich anhand der Art der zulässigen Muster gruppieren: Punktmuster im Rd: Im ersten Teil betrachten wir Punktmuster; die Figuren sind Mengen von m bzw. n Punkten im Rd. Kongruenztest: Wir geben einen Algorithmus an, der in O(n ⌈d/3 ⌉ log n) Zeit (m < n) entscheidet, ob es eine Kongruenzabbildung gibt, die P auf Q abbildet (dies kann als Spezialfall der Mustererkennungsproblems betrachtet werden, bei dem das Abstandsmaß die triviale Metrik ist). Hausdorff-Abstand: Wir beschreiben den ersten nicht-trivialen Algorithmus zur Berechnung des gerichteten Hausdorff-Abstandes h(P,Q) von einer Menge von Punkten P zu einer Menge von semialgebraischen Mengen konstanter Beschreibungskomplexität Q (dies kann als Spezialfall der Mustererkennungsproblems betrachtet werden, bei dem die Identität die einzige zulässige Transformation ist); die Laufzeit ist Oε(m nε log m+m1+ε-1/(2d-2) n). Planare Kurven: Der zweite Teil beschäftigt sich mit Mustererkennungsproblemen für polygonale Kurven in der Ebene; die Figuren sind Polygonzüge P,Q mit m bzw. n Ecken und als Abstandsmaß betrachten wir den Frechét-Abstand F(P,Q) von P und Q. Matching unter Translationen: Wir entwickeln den ersten Algorithmus, der das Matchingproblem für Polygonzüge bezüglich des Frechét-Abstandes unter Translationen löst; die Laufzeit ist O((m n)3(m+ n)2). Außerdem geben wir einen O(ε-2 m n) Approximationsalgorithmus der Güte (1+ε) für dieses Problem an, indem wir Referenzpunktmethoden verallgemeinern. Weiterhin zeigen wir, daß es für affine Abbildungen keine solchen Referenzpunkte gibt. Hausdorff- vs. Frechét-Abstand: Wir zeigen, daß für eine gewisse Klasse von Kurven ein linearer Zusammenhang zwischen dem Frechét- und dem Hausdorff-Abstand besteht. Für diese Art von Kurven geben wir einen O((m+ n) log2(m+ n) 2α(m+ n)) Approximationsalgorithmus zur Berechnung von F(P,Q) an. Schließlich beschreiben wir den ersten nicht- trivialen Algorithmus um solche Kurven zu erkennen; die Laufzeit ist O(n log2 n). Einfache polyedrische Flächen im R3: Im letzten Teil betrachten wir Muster die sich aus Mengen P und Q von m bzw. n disjunkten Dreiecken im R3 zusammensetzen. Hausdorff-Abstand: Wir entwickeln einen Algorithmus, der H(P,Q), den Hausdorff-Abstand zwischen P und Q, in Oε((m n)15/16+ε (m17/16+ n17/16)) Zeit berechnet.","abstract_html":"Das geometrische Mustererkennungsproblem besteht darin, zu zwei gegebenen Mustern P und Q aus einer Menge von zulässigen Mustern Π und einem Abstandsmaß δ für solche Muster eine Transformation τ aus einer Menge von zulässigen Transformationen T zu finden, so daß der Abstand δ(τ(P),Q) möglichst klein wird. In der Dissertation werden effiziente Algorithmen für verschiedenen Varianten dieser Problemstellung vorgestellt; die Ergebnisse lassen sich anhand der Art der zulässigen Muster gruppieren: Punktmuster im Rd: Im ersten Teil betrachten wir Punktmuster; die Figuren sind Mengen von m bzw. n Punkten im Rd. Kongruenztest: Wir geben einen Algorithmus an, der in O(n ⌈d/3 ⌉ log n) Zeit (m &lt; n) entscheidet, ob es eine Kongruenzabbildung gibt, die P auf Q abbildet (dies kann als Spezialfall der Mustererkennungsproblems betrachtet werden, bei dem das Abstandsmaß die triviale Metrik ist). Hausdorff-Abstand: Wir beschreiben den ersten nicht-trivialen Algorithmus zur Berechnung des gerichteten Hausdorff-Abstandes h(P,Q) von einer Menge von Punkten P zu einer Menge von semialgebraischen Mengen konstanter Beschreibungskomplexität Q (dies kann als Spezialfall der Mustererkennungsproblems betrachtet werden, bei dem die Identität die einzige zulässige Transformation ist); die Laufzeit ist Oε(m nε log m+m1+ε-1/(2d-2) n). Planare Kurven: Der zweite Teil beschäftigt sich mit Mustererkennungsproblemen für polygonale Kurven in der Ebene; die Figuren sind Polygonzüge P,Q mit m bzw. n Ecken und als Abstandsmaß betrachten wir den Frechét-Abstand F(P,Q) von P und Q. Matching unter Translationen: Wir entwickeln den ersten Algorithmus, der das Matchingproblem für Polygonzüge bezüglich des Frechét-Abstandes unter Translationen löst; die Laufzeit ist O((m n)3(m+ n)2). Außerdem geben wir einen O(ε-2 m n) Approximationsalgorithmus der Güte (1+ε) für dieses Problem an, indem wir Referenzpunktmethoden verallgemeinern. Weiterhin zeigen wir, daß es für affine Abbildungen keine solchen Referenzpunkte gibt. Hausdorff- vs. Frechét-Abstand: Wir zeigen, daß für eine gewisse Klasse von Kurven ein linearer Zusammenhang zwischen dem Frechét- und dem Hausdorff-Abstand besteht. Für diese Art von Kurven geben wir einen O((m+ n) log2(m+ n) 2α(m+ n)) Approximationsalgorithmus zur Berechnung von F(P,Q) an. Schließlich beschreiben wir den ersten nicht- trivialen Algorithmus um solche Kurven zu erkennen; die Laufzeit ist O(n log2 n). Einfache polyedrische Flächen im R3: Im letzten Teil betrachten wir Muster die sich aus Mengen P und Q von m bzw. n disjunkten Dreiecken im R3 zusammensetzen. Hausdorff-Abstand: Wir entwickeln einen Algorithmus, der H(P,Q), den Hausdorff-Abstand zwischen P und Q, in Oε((m n)15/16+ε (m17/16+ n17/16)) Zeit berechnet.","abstract_has_math":false,"creators":["Knauer, Christian"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2002,"date_issued":"2002","date_published":"2002","updated_at":"2026-08-21T16:44:52Z","subjects":["computational geometry","pattern matching","Fréchet distance","Hausdorff distance","straight curves","F.2.m","68Q15"],"languages":["ger"],"rights":[],"rights_urls":["http://www.fu-berlin.de/sites/refubium/rechtliches/Nutzungsbedingungen"],"identifier_entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://dx.doi.org/10.17169/refubium-16312"],"render_values":[{"text":"http://dx.doi.org/10.17169/refubium-16312","href":"http://dx.doi.org/10.17169/refubium-16312","code":true}]}]},"links":{"outbound_url":"https://refubium.fu-berlin.de/handle/fub188/12114","outbound_label":"Repository record","outbound_source":"dc:identifier.uri"},"source_record":{"url":"https://refubium.fu-berlin.de/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Arefubium.fu-berlin.de%3Afub188%2F12114","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Knauer, Christian"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.issued","label":"Date","values":["2002"]},{"key":"dc:type","label":"Dc Type","values":["doc-type:doctoralThesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["computational geometry","pattern matching","Fréchet distance","Hausdorff distance","straight curves","F.2.m","68Q15"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["ger"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://www.fu-berlin.de/sites/refubium/rechtliches/Nutzungsbedingungen"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://refubium.fu-berlin.de/handle/fub188/12114","http://dx.doi.org/10.17169/refubium-16312"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Cover and contents Glossary 1 Introduction I Point set pattern matching in d-dimensional space 2 Testing the congruence of point sets in Rd 2.1 The dimension reduction technique 2.2 A refined approach 3 Measuring the Hausdorff distance of point sets in Rd 3.1 The one-sided Hausdorff distance of a point set to a semialgebraic set II Matching of plane curves 4 Matching polygonal curves with respect to the Fréchet distance 4.1 Computing the Fréchet distance 4.2 Minimizing the Fréchet distance 4.3 Approximately minimizing the Fréchet distance 5 Bounding the Fréchet distance by the Hausdorff distance 5.1 The upper bound 5.2 Computing the reparametrization 5.3 Recognizing Κ-straight curves III Computing the Hausdorff distance between polyhedral surfaces in R3 6.1 Outline of the method 6.2 The LBP-Hausdorff distance of Δ-patterns 6.3 The Hausdorff distance of Δ-patterns Bibliography Appendices Curriculum vitae Zusammenfassung Index"]},{"key":"dc:description.abstract","label":"Abstract","values":["Das geometrische Mustererkennungsproblem besteht darin, zu zwei gegebenen Mustern P und Q aus einer Menge von zulässigen Mustern Π und einem Abstandsmaß δ für solche Muster eine Transformation τ aus einer Menge von zulässigen Transformationen T zu finden, so daß der Abstand δ(τ(P),Q) möglichst klein wird. In der Dissertation werden effiziente Algorithmen für verschiedenen Varianten dieser Problemstellung vorgestellt; die Ergebnisse lassen sich anhand der Art der zulässigen Muster gruppieren: Punktmuster im Rd: Im ersten Teil betrachten wir Punktmuster; die Figuren sind Mengen von m bzw. n Punkten im Rd. Kongruenztest: Wir geben einen Algorithmus an, der in O(n ⌈d/3 ⌉ log n) Zeit (m < n) entscheidet, ob es eine Kongruenzabbildung gibt, die P auf Q abbildet (dies kann als Spezialfall der Mustererkennungsproblems betrachtet werden, bei dem das Abstandsmaß die triviale Metrik ist). Hausdorff-Abstand: Wir beschreiben den ersten nicht-trivialen Algorithmus zur Berechnung des gerichteten Hausdorff-Abstandes h(P,Q) von einer Menge von Punkten P zu einer Menge von semialgebraischen Mengen konstanter Beschreibungskomplexität Q (dies kann als Spezialfall der Mustererkennungsproblems betrachtet werden, bei dem die Identität die einzige zulässige Transformation ist); die Laufzeit ist Oε(m nε log m+m1+ε-1/(2d-2) n). Planare Kurven: Der zweite Teil beschäftigt sich mit Mustererkennungsproblemen für polygonale Kurven in der Ebene; die Figuren sind Polygonzüge P,Q mit m bzw. n Ecken und als Abstandsmaß betrachten wir den Frechét-Abstand F(P,Q) von P und Q. Matching unter Translationen: Wir entwickeln den ersten Algorithmus, der das Matchingproblem für Polygonzüge bezüglich des Frechét-Abstandes unter Translationen löst; die Laufzeit ist O((m n)3(m+ n)2). Außerdem geben wir einen O(ε-2 m n) Approximationsalgorithmus der Güte (1+ε) für dieses Problem an, indem wir Referenzpunktmethoden verallgemeinern. Weiterhin zeigen wir, daß es für affine Abbildungen keine solchen Referenzpunkte gibt. Hausdorff- vs. Frechét-Abstand: Wir zeigen, daß für eine gewisse Klasse von Kurven ein linearer Zusammenhang zwischen dem Frechét- und dem Hausdorff-Abstand besteht. Für diese Art von Kurven geben wir einen O((m+ n) log2(m+ n) 2α(m+ n)) Approximationsalgorithmus zur Berechnung von F(P,Q) an. Schließlich beschreiben wir den ersten nicht- trivialen Algorithmus um solche Kurven zu erkennen; die Laufzeit ist O(n log2 n). Einfache polyedrische Flächen im R3: Im letzten Teil betrachten wir Muster die sich aus Mengen P und Q von m bzw. n disjunkten Dreiecken im R3 zusammensetzen. Hausdorff-Abstand: Wir entwickeln einen Algorithmus, der H(P,Q), den Hausdorff-Abstand zwischen P und Q, in Oε((m n)15/16+ε (m17/16+ n17/16)) Zeit berechnet.","The geometric shape matching problem reads as follows: given two shapes P and Q from a set of valid shapes Π and a distance measure δ for these shapes, find a transformation τ from a set of valid transformations T, such that the distance δ(τ(P),Q) is as small as possible. In this thesis we present efficient algorithms for variants of this problem; the results can be grouped according to the shapes considered: Point patterns in Rd: In the first part we consider point patterns; the shapes are point sets consisting of m and n points in Rd, respectively. Congruence test: We present an algorithm to decide in O(n ⌈d/3 ⌉ log n) time (m < n), whether there is a congruence, that maps P onto Q (this can be considered as a special case of the shape matching problem where the distance measure is the discrete metric). Hausdorff-distance: We give the first non-trivial algorithm to compute the directed Hausdorff- distance h(P,Q) from a set of points P to a set Q of semialgebraic sets of constant description complexity each (this can be considered as a special case of the shape matching problem where the identity is the only valid transformation); the runtime is Oε(m nε log m+m1+ε-1/(2d-2) n). Planar curves: The second part deals with the shape matching problem for polygonal curves in the plane; the shapes are polygonal chains P,Q with m and n vertices, respectively. The distance measure is the Frechét-distance F(P,Q) of P and Q. Matching under translations: We give the first algorithm for matching polygonal chains with respect to the Frechét-distance under translations; the runtime is O((m n)3(m+ n)2). Furthermore we describe an O(ε-2 m n) approximation algorithm of quality (1+ε) by generalizing reference-point based methods. Finally we prove that reference-points for affine maps do not exist. Hausdorff- vs. Frechét-distance: We show that the Frechét- and the Hausdorff- distance are linearly related for a certain class of curves. For curves of that type we describe an O((m+ n) log2(m+ n) 2α(m+ n)) time approximation algorithm to compute F(P,Q). We conclude with the first non-trivial algorithm to detect such curves; it runs in O(n log2 n) time. Simple polyhedral surfaces in R3: In the last part we consider shapes that are composed of sets P and Q of m and n disjoint triangles in R3. Hausdorff-distance: We develop an algorithm that computes H(P,Q), the Hausdorff-distance between P and Q, in Oε((m n)15/16+ε (m17/16+ n17/16)) time."]},{"key":"dc:title","label":"Title","values":["Algorithmen zum Vergleich geometrischer Muster"]}]}],"canonical_facts":{"dc:creator":["Knauer, Christian"],"dc:date.issued":["2002"],"dc:description":["Cover and contents Glossary 1 Introduction I Point set pattern matching in d-dimensional space 2 Testing the congruence of point sets in Rd 2.1 The dimension reduction technique 2.2 A refined approach 3 Measuring the Hausdorff distance of point sets in Rd 3.1 The one-sided Hausdorff distance of a point set to a semialgebraic set II Matching of plane curves 4 Matching polygonal curves with respect to the Fréchet distance 4.1 Computing the Fréchet distance 4.2 Minimizing the Fréchet distance 4.3 Approximately minimizing the Fréchet distance 5 Bounding the Fréchet distance by the Hausdorff distance 5.1 The upper bound 5.2 Computing the reparametrization 5.3 Recognizing Κ-straight curves III Computing the Hausdorff distance between polyhedral surfaces in R3 6.1 Outline of the method 6.2 The LBP-Hausdorff distance of Δ-patterns 6.3 The Hausdorff distance of Δ-patterns Bibliography Appendices Curriculum vitae Zusammenfassung Index"],"dc:description.abstract":["Das geometrische Mustererkennungsproblem besteht darin, zu zwei gegebenen Mustern P und Q aus einer Menge von zulässigen Mustern Π und einem Abstandsmaß δ für solche Muster eine Transformation τ aus einer Menge von zulässigen Transformationen T zu finden, so daß der Abstand δ(τ(P),Q) möglichst klein wird. In der Dissertation werden effiziente Algorithmen für verschiedenen Varianten dieser Problemstellung vorgestellt; die Ergebnisse lassen sich anhand der Art der zulässigen Muster gruppieren: Punktmuster im Rd: Im ersten Teil betrachten wir Punktmuster; die Figuren sind Mengen von m bzw. n Punkten im Rd. Kongruenztest: Wir geben einen Algorithmus an, der in O(n ⌈d/3 ⌉ log n) Zeit (m < n) entscheidet, ob es eine Kongruenzabbildung gibt, die P auf Q abbildet (dies kann als Spezialfall der Mustererkennungsproblems betrachtet werden, bei dem das Abstandsmaß die triviale Metrik ist). Hausdorff-Abstand: Wir beschreiben den ersten nicht-trivialen Algorithmus zur Berechnung des gerichteten Hausdorff-Abstandes h(P,Q) von einer Menge von Punkten P zu einer Menge von semialgebraischen Mengen konstanter Beschreibungskomplexität Q (dies kann als Spezialfall der Mustererkennungsproblems betrachtet werden, bei dem die Identität die einzige zulässige Transformation ist); die Laufzeit ist Oε(m nε log m+m1+ε-1/(2d-2) n). Planare Kurven: Der zweite Teil beschäftigt sich mit Mustererkennungsproblemen für polygonale Kurven in der Ebene; die Figuren sind Polygonzüge P,Q mit m bzw. n Ecken und als Abstandsmaß betrachten wir den Frechét-Abstand F(P,Q) von P und Q. Matching unter Translationen: Wir entwickeln den ersten Algorithmus, der das Matchingproblem für Polygonzüge bezüglich des Frechét-Abstandes unter Translationen löst; die Laufzeit ist O((m n)3(m+ n)2). Außerdem geben wir einen O(ε-2 m n) Approximationsalgorithmus der Güte (1+ε) für dieses Problem an, indem wir Referenzpunktmethoden verallgemeinern. Weiterhin zeigen wir, daß es für affine Abbildungen keine solchen Referenzpunkte gibt. Hausdorff- vs. Frechét-Abstand: Wir zeigen, daß für eine gewisse Klasse von Kurven ein linearer Zusammenhang zwischen dem Frechét- und dem Hausdorff-Abstand besteht. Für diese Art von Kurven geben wir einen O((m+ n) log2(m+ n) 2α(m+ n)) Approximationsalgorithmus zur Berechnung von F(P,Q) an. Schließlich beschreiben wir den ersten nicht- trivialen Algorithmus um solche Kurven zu erkennen; die Laufzeit ist O(n log2 n). Einfache polyedrische Flächen im R3: Im letzten Teil betrachten wir Muster die sich aus Mengen P und Q von m bzw. n disjunkten Dreiecken im R3 zusammensetzen. Hausdorff-Abstand: Wir entwickeln einen Algorithmus, der H(P,Q), den Hausdorff-Abstand zwischen P und Q, in Oε((m n)15/16+ε (m17/16+ n17/16)) Zeit berechnet.","The geometric shape matching problem reads as follows: given two shapes P and Q from a set of valid shapes Π and a distance measure δ for these shapes, find a transformation τ from a set of valid transformations T, such that the distance δ(τ(P),Q) is as small as possible. In this thesis we present efficient algorithms for variants of this problem; the results can be grouped according to the shapes considered: Point patterns in Rd: In the first part we consider point patterns; the shapes are point sets consisting of m and n points in Rd, respectively. Congruence test: We present an algorithm to decide in O(n ⌈d/3 ⌉ log n) time (m < n), whether there is a congruence, that maps P onto Q (this can be considered as a special case of the shape matching problem where the distance measure is the discrete metric). Hausdorff-distance: We give the first non-trivial algorithm to compute the directed Hausdorff- distance h(P,Q) from a set of points P to a set Q of semialgebraic sets of constant description complexity each (this can be considered as a special case of the shape matching problem where the identity is the only valid transformation); the runtime is Oε(m nε log m+m1+ε-1/(2d-2) n). Planar curves: The second part deals with the shape matching problem for polygonal curves in the plane; the shapes are polygonal chains P,Q with m and n vertices, respectively. The distance measure is the Frechét-distance F(P,Q) of P and Q. Matching under translations: We give the first algorithm for matching polygonal chains with respect to the Frechét-distance under translations; the runtime is O((m n)3(m+ n)2). Furthermore we describe an O(ε-2 m n) approximation algorithm of quality (1+ε) by generalizing reference-point based methods. Finally we prove that reference-points for affine maps do not exist. Hausdorff- vs. Frechét-distance: We show that the Frechét- and the Hausdorff- distance are linearly related for a certain class of curves. For curves of that type we describe an O((m+ n) log2(m+ n) 2α(m+ n)) time approximation algorithm to compute F(P,Q). We conclude with the first non-trivial algorithm to detect such curves; it runs in O(n log2 n) time. Simple polyhedral surfaces in R3: In the last part we consider shapes that are composed of sets P and Q of m and n disjoint triangles in R3. Hausdorff-distance: We develop an algorithm that computes H(P,Q), the Hausdorff-distance between P and Q, in Oε((m n)15/16+ε (m17/16+ n17/16)) time."],"dc:identifier.uri":["https://refubium.fu-berlin.de/handle/fub188/12114","http://dx.doi.org/10.17169/refubium-16312"],"dc:language":["ger"],"dc:rights.uri":["http://www.fu-berlin.de/sites/refubium/rechtliches/Nutzungsbedingungen"],"dc:subject":["computational geometry","pattern matching","Fréchet distance","Hausdorff distance","straight curves","F.2.m","68Q15"],"dc:title":["Algorithmen zum Vergleich geometrischer Muster"],"dc:type":["doc-type:doctoralThesis"]},"updated_at":"2026-08-21T16:44:52Z"}