OPTIMAL BINARY SPACE PARTITIONS FOR SEGMENTS IN THE PLANE
From MaRDI portal
Publication:5299997
DOI10.1142/S0218195912500045zbMath1267.68268OpenAlexW2115754974MaRDI QIDQ5299997
Amirali Khosravi, Mark T. de Berg
Publication date: 24 June 2013
Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0218195912500045
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Upward Planar Drawings with Three and More Slopes ⋮ Reconstruction of Weakly Simple Polygons from Their Edges ⋮ Upward planar drawings with three and more slopes ⋮ Planar straight-line realizations of 2-trees with prescribed edge lengths ⋮ Parameterized complexity of the MinCCA problem on graphs of bounded decomposability ⋮ Extending Partial Orthogonal Drawings ⋮ \((k,p)\)-planarity: a relaxation of hybrid planarity ⋮ Complexity of domination in triangulated plane graphs ⋮ The dispersive art gallery problem ⋮ Complexity results on untangling red-blue matchings ⋮ On compatible triangulations with a minimum number of Steiner points ⋮ Exact algorithms and hardness results for geometric red-blue hitting set problem ⋮ Recognizing DAGs with page-number 2 is NP-complete ⋮ Unit-length rectangular drawings of graphs ⋮ Snapping Graph Drawings to the Grid Optimally ⋮ Extending simple drawings ⋮ Minimum Weight Connectivity Augmentation for Planar Straight-Line Graphs ⋮ Ordered Level Planarity, Geodesic Planarity and Bi-Monotonicity ⋮ On simplified NP-complete variants of \textsc{Monotone} 3\textsc{-Sat} ⋮ Independent dominating set problem revisited ⋮ On the proper orientation number of bipartite graphs ⋮ On the geometric red-blue set cover problem ⋮ Dispersing and grouping points on planar segments ⋮ Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames ⋮ Maximum Area Axis-Aligned Square Packings. ⋮ Particle-based assembly using precise global control ⋮ Particle-based assembly using precise global control ⋮ Minimum weight connectivity augmentation for planar straight-line graphs ⋮ Polygon simplification by minimizing convex corners ⋮ The partial visibility representation extension problem ⋮ Recognizing DAGs with page-number 2 is NP-complete ⋮ Producing genomic sequences after genome scaffolding with ambiguous paths: complexity, approximation and lower bounds ⋮ Complexity of fall coloring for restricted graph classes ⋮ On the minimum consistent subset problem ⋮ Level-planar drawings with few slopes ⋮ The Monotone Satisfiability Problem with Bounded Variable Appearances ⋮ Drawing Clustered Planar Graphs on Disk Arrangements ⋮ Regular augmentation of planar graphs ⋮ Multilevel Planarity ⋮ Multi-colored spanning graphs ⋮ Planar 3-SAT with a clause/variable cycle ⋮ Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames ⋮ Extending Partial Orthogonal Drawings
Cites Work
- Unnamed Item
- Binary plane partitions for disjoint line segments
- Perfect binary space partitions
- Efficient binary space partitions for hidden-surface removal and solid modeling
- On the optimal binary plane partition for sets of isothetic rectangles
- A note on binary plane partitions
- Linear size binary space partitions for uncluttered scenes
- On optimal cuts of hyperrectangles
- OPTIMAL BSPs AND RECTILINEAR CARTOGRAMS
- Planar Formulae and Their Uses
- Optimal binary space partitions for orthogonal objects
- The Problem of Compatible Representatives
