Optimal Binary Space Partitions for Segments in the Plane

No abstract is available for this paper.

• Publication year

  2012

• Venue

  International journal of computational geometry and applications

• Publication date

  2012-10-16

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1142/S0218195912500045
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Binary Plane Partitions for Disjoint Line Segments

  2009cited by this paper
• An algorithmic study of switch graphs

  2009cited by this paper
• Binary Space Partitions: recent Developments

  2007cited by this paper
• Binary Space Partitions

  2006cited by this paper
• Optimal BSPs and rectilinear cartograms

  2006cited by this paper
• A Note on Binary Plane Partitions

  2001cited by this paper
• Linear Size Binary Space Partitions for Uncluttered Scenes

  2000cited by this paper
• Computational geometry: algorithms and applications

  1997cited by this paper
• On optimal cuts of hyperrectangles

  1995cited by this paper
• Perfect Binary Space Partitions

  1993cited by this paper
• The Problem of Compatible Representatives

  1992cited by this paper
• On the Optimal Binary Plane Partition for Sets of Isothetic Rectangles

  1992cited by this paper
• Optimal binary space partitions for orthogonal objects

  1990cited by this paper
• Efficient binary space partitions for hidden-surface removal and solid modeling

  1990cited by this paper
• Planar Formulae and Their Uses

  1982cited by this paper
• The NP-Completeness Column: An Ongoing Guide

  1982cited by this paper
• Computers and Intractability: A Guide to the Theory of NP-Completeness

  1979cited by this paper
• Johnson: computers and intractability: a guide to the theory of np- completeness (freeman

  1979cited by this paper

• NP-Completeness and Physical Zero-Knowledge Proof of Hotaru Beam

  2026influential citation
• Guarding Polyominoes Under k-Hop Visibility

  2025cites this paper
• Optimizing Wiggle in Storylines

  2025cites this paper
• Flipping odd matchings in geometric and combinatorial settings

  2025cites this paper
• Moving Matter: Efficient Reconfiguration of Tile Arrangements by a Single Active Robot

  2025cites this paper
• Tractable Graph Structures in EFX Orientation

  2025cites this paper
• Approximate Light Spanners in Planar Graphs

  2025cites this paper
• On Triangular Separation of Bichromatic Point Sets

  2025cites this paper
• Eliminating Majority Illusions

  2025cites this paper
• On the geometric red-blue set cover problem

  2025cites this paper
• Efficient Reconfiguration of Tile Arrangements by a Single Active Robot

  2025cites this paper
• Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths

  2024cites this paper
• Clustered Planarity Variants for Level Graphs

  2024cites this paper
• Reconfiguration of unit squares and disks: PSPACE-hardness in simple settings

  2024cites this paper
• Sliding Squares in Parallel

  2024cites this paper
• Multipacking in Euclidean Metric Space

  2024cites this paper
• Computing Conforming Partitions with Low Stabbing Number for Rectilinear Polygons

  2024influential citation
• From Planar via Outerplanar to Outerpath - Engineering NP-Hardness Constructions (Poster Abstract)

  2024cites this paper
• Dispersive Vertex Guarding for Simple and Non-Simple Polygons

  2024cites this paper
• Hardness of Packing, Covering and Partitioning Simple Polygons with Unit Squares

  2024cites this paper
• On k-Plane Insertion into Plane Drawings

  2024cites this paper
• Testing the planar straight-line realizability of 2-trees with prescribed edge lengths

  2023cites this paper
• On Layered Area-Proportional Rectangle Contact Representations

  2023cites this paper
• Complexity Results on Untangling Red-Blue Matchings

  2022cites this paper
• Double Choco is NP-complete

  2022cites this paper
• Complexity Results on Untangling Planar Rectilinear Red-Blue Matchings

  2022cites this paper
• The Dispersive Art Gallery Problem

  2022cites this paper
• Unit-length Rectangular Drawings of Graphs

  2022cites this paper
• Efficiently reconfiguring a connected swarm of labeled robots

  2022cites this paper
• Recognizing DAGs with Page-Number 2 is NP-complete

  2022cites this paper
• Producing Genomic Sequences after Genome Scaffolding with Ambiguous Paths: Complexity, Approximation and Lower Bounds

  2021cites this paper
• Particle-Based Assembly Using Precise Global Control

  2021cites this paper
• Upward Planar Drawings with Three Slopes

  2021cites this paper
• On the Geometric Red-Blue Set Cover Problem

  2021cites this paper
• On simplified NP-complete variants of Monotone3-Sat

  2021cites this paper
• Connected coordinated motion planning with bounded stretch

  2021cites this paper
• ZHED is NP-complete

  2021cites this paper
• Compacting Squares

  2021cites this paper
• Dispersing and grouping points on planar segments

  2021cites this paper
• Planar Straight-line Realizations of 2-Trees with Prescribed Edge Lengths

  2021cites this paper
• Upward Planar Drawings with Three and More Slopes

  2021cites this paper
• Packing and Covering with Segments

  2020cites this paper
• On Two-Handed Planar Assembly Partitioning with Connectivity Constraints

  2020influential citation
• Extending Partial Orthogonal Drawings

  2020cites this paper
• Geometric Graph Drawing Algorithms - Theory, Engineering and Experiments

  2020cites this paper
• Drawing Clustered Planar Graphs on Disk Arrangements

  2020cites this paper
• WALCOM: Algorithms and Computation: 14th International Conference, WALCOM 2020, Singapore, Singapore, March 31 – April 2, 2020, Proceedings

  2020cites this paper
• Level-Planar Drawings with Few Slopes

  2019cites this paper
• Simplicial Depth for Multiple Query Points

  2019cites this paper
• Constrained Orthogonal Segment Stabbing

  2019cites this paper
• Complexity of Fall Coloring for Restricted Graph Classes

  2019cites this paper
• On simplified NP-complete variants of Not-All-Equal 3-Sat and 3-Sat

  2019cites this paper
• Extending Simple Drawings

  2019cites this paper
• The k-Fréchet distance revisited and extended

  2019cites this paper
• The k-Fréchet distance

  2019cites this paper
• New Results on a Family of Geometric Hitting Set Problems in the Plane

  2019cites this paper
• Balanced Covering Problem in Bicolored point Sets

  2019cites this paper
• Maximum Area Axis-Aligned Square Packings

  2018cites this paper
• Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames

  2018cites this paper
• Volumetric covering print-paths for additive manufacturing of 3D models

  2018cites this paper
• Approximating Dominating Set on Intersection Graphs of L-frames

  2018cites this paper
• Planar Steiner Orientation is NP-complete

  2018cites this paper
• Consistent Subset Problem with Two Labels

  2018cites this paper
• New Results About the Linearization of Scaffolds Sharing Repeated Contigs

  2018cites this paper
• (k, p)-Planarity: A Generalization of Hybrid Planarity

  2018cites this paper
• Drawing Clustered Graphs on Disk Arrangements

  2018cites this paper
• Multilevel Planarity

  2018cites this paper
• On the Minimum Consistent Subset Problem

  2018cites this paper
• (k, p)-Planarity: A Relaxation of Hybrid Planarity

  2018cites this paper
• 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, Liverpool, UK, August 27-31, 2018

  2018cites this paper
• Planar 3-SAT with a Clause/Variable Cycle

  2017influential citation
• Complexity of domination in triangulated plane graphs

  2017cites this paper
• Towards a Topology-Shape-Metrics Framework for Ortho-Radial Drawings

  2017cites this paper
• Ordered Level Planarity and Geodesic Planarity

  2017influential citation
• Straight Line Movement in Morphing and Pursuit Evasion

  2017cites this paper
• Ordered Level Planarity and Its Relationship to Geodesic Planarity, Bi-Monotonicity, and Variations of Level Planarity

  2017influential citation
• Distance-preserving graph contractions

  2017influential citation
• Obedient Plane Drawings for Disk Intersection Graphs

  2017cites this paper
• On Compatible Triangulations with a Minimum Number of Steiner Points

  2017cites this paper
• On planar variants of the monotone satisfiability problem with bounded variable appearances

  2016cites this paper
• Reconstruction of Weakly Simple Polygons from their Edges

  2016cites this paper
• Polygon Simplification by Minimizing Convex Corners

  2016cites this paper
• Parameterized complexity of the MINCCA problem on graphs of bounded decomposability

  2016cites this paper
• Orthogonal layout with optimal face complexity

  2016cites this paper
• Multi-colored Spanning Graphs

  2016influential citation
• Bend Minimization of Ortho-Radial Graph Drawings

  2016cites this paper
• Minimum Weight Connectivity Augmentation for Planar Straight-Line Graphs

  2016cites this paper
• Snapping Graph Drawings to the Grid Optimally

  2016influential citation
• New Approaches to Classic Graph-Embedding Problems - Orthogonal Drawings & Constrained Planarity

  2015cites this paper
• Regular Augmentation of Planar Graphs

  2015influential citation
• The Partial Visibility Representation Extension Problem

  2015influential citation
• Independent dominating set problem revisited

  2015cites this paper
• Orthogonal Layout with Optimal Face Complexity : NP-hardness and Polynomial-time Algorithms

  2015influential citation
• 12th Cologne-Twente workshop on graphs and combinatorial optimization (CTW 2013)

  2015cites this paper
• Interference-free memory assignment in multi-core chips is NP-hard

  2014cites this paper
• Simultaneous Embeddability of Two Partitions

  2014cites this paper
• Complexity of Higher-Degree Orthogonal Graph Embedding in the Kandinsky Model

  2014cites this paper
• Interference-free memory assignment in multi-core chips is NP-hard (回路とシステム)

  2014cites this paper
• Detection number of bipartite graphs and cubic graphs

  2014cites this paper
• On the proper orientation number of bipartite graphs

  2014influential citation