Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Graph Profile Realizations and Applications to Social Networks Read chapter Read first chapter

2019 | OriginalPaper | Chapter

Matching Sets of Line Segments

Authors : Hyeyun Yang, Antoine Vigneron

Published in: WALCOM: Algorithms and Computation

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We give approximation algorithms for matching two sets of line segments in constant dimension. We consider several versions of the problem: Hausdorff distance, bottleneck distance and largest common point set. We study these similarity measures under several sets of transformations: translations, rotations about a fixed point and rigid motions. As opposed to previous theoretical work on this problem, we match segments individually, in other words we regard our two input sets as sets of segments rather than unions of segments.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Linear Pseudo-Polynomial Factor Algorithm for Automaton Constrained Tree Knapsack Problem
next chapter Efficient Algorithm for Box Folding
Literature
1.
Ahn, H., Cheong, O., Park, C., Shin, C., Vigneron, A.: Maximizing the overlap of two planar convex sets under rigid motions. Comput. Geom. 37(1), 3–15 (2007)MathSciNetCrossRef
2.
Alt, H., Behrends, B., Blömer, J.: Approximate matching of polygonal shapes. Ann. Math. Artif. Intell. 13(3), 251–265 (1995)MathSciNetCrossRef
3.
Alt, H., Guibas, L.J.: Discrete geometric shapes: matching, interpolation, and approximation. In: Sack, J.R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 121–153. B.V. North-Holland, Amsterdam (2000). Chapter 3CrossRef
4.
Alt, H., Mehlhorn, K., Wagener, H., Welzl, E.: Congruence, similarity, and symmetries of geometric objects. Discrete Comput. Geom. 3(3), 237–256 (1988)MathSciNetCrossRef
5.
Arya, S., Mount, D.M., Netanyahu, N.S., Silverman, R., Wu, A.Y.: An optimal algorithm for approximate nearest neighbor searching fixed dimensions. J. ACM 45(6), 891–923 (1998)MathSciNetCrossRef
6.
Cabello, S., de Berg, M., Giannopoulos, P., Knauer, C., van Oostrum, R., Veltkamp, R.C.: Maximizing the area of overlap of two unions of disks under rigid motion. Int. J. Comput. Geom. Appl. 19(6), 533–556 (2009)MathSciNetCrossRef
7.
Chen, H.H., Huang, T.S.: Matching 3-D line segments with applications to multiple-object motion estimation. IEEE Trans. Pattern Anal. Mach. Intell. 12(10), 1002–1008 (1990)CrossRef
8.
Chew, L., Goodrich, M.T., Huttenlocher, D.P., Kedem, K., Kleinberg, J.M., Kravets, D.: Geometric pattern matching under Euclidean motion. Comput. Geom. 7(1), 113–124 (1997)MathSciNetCrossRef
9.
Efrat, A., Itai, A., Katz, M.J.: Geometry helps in bottleneck matching and related problems. Algorithmica 31(1), 1–28 (2001)MathSciNetCrossRef
10.
Gao, M., Skolnick, J.: iAlign: a method for the structural comparison of protein-protein interfaces. Bioinformatics 26(18), 2259–2265 (2010)CrossRef
11.
Har-Peled, S., Roy, S.: Approximating the maximum overlap of polygons under translation. Algorithmica 78(1), 147–165 (2017)MathSciNetCrossRef
12.
Heffernan, P.J., Schirra, S.: Approximate decision algorithms for point set congruence. Comput. Geom. 4(3), 137–156 (1994)MathSciNetCrossRef
13.
Medioni, G.G., Nevatia, R.: Matching images using linear features. IEEE Trans. Pattern Anal. Mach. Intell. 6(6), 675–685 (1984)CrossRef
14.
Vigneron, A.: Geometric optimization and sums of algebraic functions. ACM Trans. Algorithms 10(1), 4:1–4:20 (2014)MathSciNetCrossRef
15.
Yon, J., Cheng, S., Cheong, O., Vigneron, A.: Finding largest common point sets. Int. J. Comput. Geom. Appl. 27(3), 177–186 (2017)MathSciNetCrossRef
Metadata
Title
Matching Sets of Line Segments
Authors
Hyeyun Yang
Antoine Vigneron
Copyright Year
2019
Book
WALCOM: Algorithms and Computation

Print ISBN: 978-3-030-10563-1

Electronic ISBN: 978-3-030-10564-8

Copyright Year: 2019

DOI
https://doi.org/10.1007/978-3-030-10564-8_21

Premium Partner

    Image Credits