Back to Search
Start Over
Intersections and circuits in sets of line segments
- Source :
- Journal of Combinatorial Optimization. 44:2302-2323
- Publication Year :
- 2021
- Publisher :
- Springer Science and Business Media LLC, 2021.
-
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.
- Subjects :
- Control and Optimization
Computer science
Applied Mathematics
Structure (category theory)
Image processing
Upper and lower bounds
Computer Science Applications
Planar graph
Combinatorics
symbols.namesake
Line segment
Computational Theory and Mathematics
Intersection
Theory of computation
symbols
Discrete Mathematics and Combinatorics
Geometric modeling
MathematicsofComputing_DISCRETEMATHEMATICS
Subjects
Details
- ISSN :
- 15732886 and 13826905
- Volume :
- 44
- Database :
- OpenAIRE
- Journal :
- Journal of Combinatorial Optimization
- Accession number :
- edsair.doi...........2a49e59041c878e3fc5b890825f9a689