Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Theory of Computing Systems

17.08.2018

Capturing Points with a Rotating Polygon (and a 3D Extension)

Erschienen in: Theory of Computing Systems | Ausgabe 3/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We study the problem of rotating a simple polygon to contain the maximum number of elements from a given point set in the plane. We consider variations of this problem where the rotation center is a given point or lies on a segment or a line. We also solve an extension to 3D where we rotate a polyhedron around a given point to contain the maximum number of elements from a set of points in the space.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Literatur
1.
Agarwal, P.K., Flato, E., Halperin, D.: Polygon decomposition for efficient construction of Minkowski sums. Comput. Geom. Theory Appl. 21(1–2), 39–61 (2002)MathSciNetCrossRefMATH
2.
Agarwal, P.K., Hagerup, T., Ray, R., Sharir, M., Smid, M., Welzl, E.: Translating a planar object to maximize point containment. In: Algorithms — ESA 2002: 10th Annual European Symposium. Rome, Italy, September 17–21, 2002. Proceedings, pp. 42–53 (2002)
3.
4.
Barequet, G., Dickerson, M., Pau, P.: Translating a convex polygon to contain a maximum number of points. Comput. Geom. Theory Appl. 8(4), 167–179 (1997)MathSciNetCrossRefMATH
5.
Barequet, G., Goryachev, A.: Offset polygon and annulus placement problems. Comput. Geom. Theory Appl. 47(3, Part A), 407–434 (2014)MathSciNetCrossRefMATH
6.
Barequet, G., Har-Peled, S.: Polygon containment and translation min-Hausdorff-distance between segment sets are 3SUM-hard. Int. J. Comput. Geom. Appl. 11(4), 465–474 (2001)CrossRefMATH
7.
Chazelle, B.: Advances in Computing Research, vol. 1, Chapter The polygon containment problem, pp. 1–33. JAI Press (1983)
8.
Dickerson, M., Scharstein, D.: Optimal placement of convex polygons to maximize point containment. Comput. Geom. Theory Appl. 11(1), 1–16 (1998)MathSciNetCrossRefMATH
9.
Gajentaan, A., Overmars, M.H.: On a class of O(n 2) problems in computational geometry. Comput. Geom. Theory nd Appl. 5(3), 165–185 (1995)CrossRefMATH
10.
11.
Ishiguro, H., Yamamoto, M., Tsuji, S.: Omni-directional stereo. IEEE Trans. Pattern Anal. Mach. Intell. 14(2), 257–262 (1992)CrossRef
12.
Kopelowitz, T., Pettie, S., Porat, E.: Higher lower bounds from the 3SUM conjecture. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1272–1287. Society for Industrial and Applied Mathematics (2016)
13.
analysis, Tristan Needham.: Visual Complex Chapter 6.II.3: A Conformal Map of the Sphere, pp 283–286. Clarendon Press, Oxford (1998)
14.
Pǎtraṡcu, M.: Towards polynomial lower bounds for dynamic problems. In: Proceedings of the Forty-Second ACM Symposium on Theory of Computing, pp. 603–610. ACM (2010)
15.
Yap, C.K., Chang, E.-C.: Algorithms for Robot Motion Planning and Manipulation, Chapter Issues in the Metrology of Geometric Tolerancing, pp 393–400. Wellesley, A.K. Peters (1997)
Metadaten
Titel
Capturing Points with a Rotating Polygon (and a 3D Extension)
Publikationsdatum
17.08.2018
Erschienen in
Theory of Computing Systems / Ausgabe 3/2019
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-018-9885-y