nach oben

Journal of Combinatorial Optimization

Erschienen in:

10.04.2021

Intersections and circuits in sets of line segments

verfasst von: Boris Brimkov, Jesse Geneson, Alathea Jensen, Jordan Broussard, Pouria Salehi Nowbandegani

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 4/2022

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Sets of straight line segments with special structures and properties appear in various applications of geometric modeling, such as scientific visualization, computer-aided design, and medical image processing. In this paper, we derive sharp upper and lower bounds on the number of intersection points and closed regions that can occur in sets of line segments with certain structure, in terms of the number of segments. In particular, we consider sets of segments whose underlying planar graphs are Halin graphs, cactus graphs, maximal planar graphs, and triangle-free planar graphs, as well as randomly produced segment sets.

Vorheriger Artikel Principal–agent problem under the linear contract

Nächster Artikel Regularized graph cuts based discrete tomography reconstruction methods

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

A graph is maximal outerplanar if it has a plane embedding in which all vertices belong to the outer face, and adding any edge to the graph causes it to no longer have this property.

We use this nomenclature instead of triangle-free graph in order to avoid confusion between geometric and graph theoretic triangles.

The nomenclature is derived from Buffon’s Needle Problem, which investigates the probability that a needle will fall on a line when dropped on a sheet with equally spaced lines.

Balaban IJ (1995) An optimal algorithm for finding segment intersections. In Proceedings of the eleventh annual symposium on computational geometry, pp. 211–219

Ben-Moshe B, Dvir A, Segal M, Tamir A (2012) Centdian computation in cactus graphs. J Gr Algorithms Appl 16(2):199–224MathSciNetCrossRef

Bentley JL, Ottmann TA (1979) Algorithms for reporting and counting geometric intersections. IEEE Trans Computers 9:643–647CrossRef

Bose P, Maheshwari A, Morin P, Morrison J, Smid M, Vahrenhold J (2007) Space-efficient geometric divide-and-conquer algorithms. Comput Geom 37(3):209–227MathSciNetCrossRef

Brévilliers M, Chevallier N, Schmitt D (2007) Triangulations of line segment sets in the plane. In International conference on foundations of software technology and theoretical computer science, pp. 388–399

Brimkov B (2017) On sets of line segments featuring a cactus structure. In International workshop on combinatorial image analysis, pp. 30–39

Brimkov B, Hicks IV (2017) Memory efficient algorithms for cactus graphs and block graphs. Discrete Appl Math 216:393–407MathSciNetCrossRef

Brimkov VE (2013) Approximability issues of guarding a set of segments. Int J Computer Math 90(8):1653–1667CrossRef

Brimkov VE, Leach A, Mastroianni M, Wu J (2011) Guarding a set of line segments in the plane. Theor Computer Sci 412(15):1313–1324MathSciNetCrossRef

Brimkov VE, Leach A, Wu J, Mastroianni M (2012) Approximation algorithms for a geometric set cover problem. Discrete Appl Mathematics 160:1039–1052MathSciNetCrossRef

Chan TM, Chen EY (2010) Optimal in-place and cache-oblivious algorithms for 3-d convex hulls and 2-d segment intersection. Comput Geom 43(8):636–646MathSciNetCrossRef

Chazelle BM (1983) Reporting and counting arbitrary planar intersections. Report CS-83-16, Department of Computer Science, Brown University, Providence, RI, USA

Chen EY, Chan TM (2003) A space-efficient algorithm for line segment intersection. In: Proceedings of the 15th Canadian conference on computational geometry, pp. 68–71

Cornuéjols G, Naddef D, Pulleyblank WR (1983) Halin graphs and the travelling salesman problem. Math Program 26(3):287–294MathSciNetCrossRef

Dujmović V, Eppstein D, Suderman M, Wood DR (2007) Drawings of planar graphs with few slopes and segments. Comput Geom 38(3):194–212MathSciNetCrossRef

de Castro N, Cobos FJ, Dana JC, Márquez A, Noy M (2002) Triangle-free planar graphs and segment intersection graphs. J Gr Algorithms Appl 6(1):7–26MathSciNetCrossRef

Durocher S, Mondal D (2018) Drawing plane triangulations with few segments. Comput Geom 77:40–45MathSciNetMATH

Eppstein D (2016) Simple recognition of Halin graphs and their generalizations. J Gr Algorithms Appl 20(2):323–346MathSciNetCrossRef

Francis MC, Kratochvíl J, Vyskočil T (2012) Segment representation of a subclass of co-planar graphs. Discrete Math 312(10):1815–1818MathSciNetCrossRef

Green B, Tao T (2013) On sets defining few ordinary lines. Discrete Comput Geom 50(2):409–468MathSciNetCrossRef

Harary F, Uhlenbeck G (1953) On the number of Husimi trees: I. Proc Nat Acad Sci 39:315–322MathSciNetCrossRef

Horton SB, Parker RG (1995) On Halin subgraphs and supergraphs. Discrete Appl Math 56(1):19–35MathSciNetCrossRef

Husimi K (1950) Note on Mayers’ theory of cluster integrals. J Chem Phys 18:682–684MathSciNetCrossRef

Igamberdiev, A, Meulemans W, Schulz A (2015) Drawing planar cubic 3-connected graphs with few segments: algorithms and experiments. In International symposium on graph drawing and network visualization, pp. 113–124

Kára J, Kratochvíl J (2006) Fixed parameter tractability of independent set in segment intersection graphs. In International workshop on parameterized and exact computation, pp. 166–174

Kariv O, Hakimi SL (1979) An algorithmic approach to network location problems. I: the p-center. SIAM J Appl Math 37(3):513–538MathSciNetCrossRef

Koontz WLG (1980) Economic evaluation of loop feeder relief alternatives. Bell Syst Tech J 59(3):277–281CrossRef

Kumar CP (2019) On the regions formed by the diagonals of a convex polygon. arXiv:1904.04065

Mairson HG, Stolfi J (1988) Reporting and counting intersections between two sets of line segments. In: Earnshaw RA (ed) Theoretical foundations of computer graphics and CAD. Springer, Berlin, pp 307–325CrossRef

Oliveros D, O’Neill C, Zerbib S (2020) The geometry and combinatorics of discrete line segment hypergraphs. Discrete Math 343(6):111825MathSciNetCrossRef

Poonen B, Rubinstein M (1998) The number of intersection points made by the diagonals of a regular polygon. SIAM J Discrete Math 11(1):135–156MathSciNetCrossRef

Preparata F, Shamos MI (2012) Computational geometry: an introduction. Springer, New YorkMATH

Rappaport D, Imai H, Toussaint GT (1990) Computing simple circuits from a set of line segments. Discrete Comput Geom 5(3):289–304MathSciNetCrossRef

Samee MAH, Alam MJ, Adnan MA, Rahman MS (2008) Minimum segment drawings of series-parallel graphs with the maximum degree three. In International symposium on graph drawing, pp. 408–419

Sysło MM, Proskurowski A (1983) On Halin graphs. In: Graph theory, Springer, Berlin, pp 248–256

Tiernan JC (1970) An efficient search algorithm to find the elementary circuits of a graph. Commun ACM 13:722–726MathSciNetCrossRef

Vahrenhold J (2007) Line-segment intersection made in-place. Comput Geom 38:213–230MathSciNetCrossRef

Wagner K (1936) Bemerkungen zum Vierfarbenproblem. Jahresbericht der Deutschen Mathematiker-Vereinigung 46:26–32MATH

Titel: Intersections and circuits in sets of line segments
verfasst von: Boris Brimkov
Jesse Geneson
Alathea Jensen
Jordan Broussard
Pouria Salehi Nowbandegani
Publikationsdatum: 10.04.2021
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 4/2022
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-021-00731-3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 4/2022

On zero-error codes produced by greedy algorithms

An integrated model for medical expense system optimization during diagnosis process based on artificial intelligence algorithm

Approximation algorithms with constant ratio for general cluster routing problems

Uniform Voronoi tessellation of digital manifolds: a GPU-based algorithm with applications to remeshing

Bicriteria streaming algorithms to balance gain and cost with cardinality constraint

The spherical k-means++ algorithm via local search scheme

Premium Partner