Binary Space Partitions for Disjoint Line Segments

Author

Your Name

Published

February 8, 2025

Introduction

Binary Space Partition (BSP) Definition

A binary space partition (BSP) is a hierarchical method for decomposing space. It recursively divides space, and objects within it, using hyperplanes. This process continues, clipping objects against these hyperplanes and recursing within the resulting half-spaces. The complexity of a BSP is measured by the number of fragments created from the initial objects. This lecture explores binary space partitions for sets of disjoint line segments in the plane, aiming to construct BSPs of minimal size.

Applications of BSPs

BSPs were initially developed in computer graphics to manage the rendering order of objects, particularly for hidden surface removal and z-buffering. Their simplicity and efficiency have led to applications in various fields.

Computer Graphics: Hidden Surface Removal and Z-buffering

In computer graphics, BSPs are instrumental in resolving the hidden surface problem. By constructing a BSP, polygons in a 3D scene can be ordered from back to front, allowing for efficient rendering by drawing only the visible surfaces. This ordering also facilitates z-buffering, a technique used to determine the visibility of objects pixel by pixel.

Solid Modeling

BSPs are used in solid modeling to represent and manipulate 3D shapes. They provide a way to decompose complex shapes into simpler convex regions, which is useful for operations like set operations (union, intersection, difference) and point-in-solid tests.

Shadow Generation

Generating shadows efficiently in computer graphics is another application of BSPs. By using BSPs, it’s possible to determine which surfaces are occluded from a light source and thus should be in shadow. BSPs can be used to create shadow volumes or shadow maps for realistic shadow rendering.

Motion Planning

In robotics and virtual environments, motion planning involves finding a path for a robot or agent to move from one location to another without colliding with obstacles. BSPs can represent the environment and the obstacles, allowing for efficient path planning algorithms by searching through the BSP space.

Range Searching

BSPs can be adapted for range searching in spatial databases. Given a set of points or objects in space, range searching involves finding all objects within a specified query region. BSPs can accelerate range queries by quickly pruning parts of the space that do not intersect the query region.

Network Design

In network design, particularly in wireless and sensor networks, BSPs can be used to solve geometric optimization problems. For example, in coverage problems or interference analysis, BSPs can help partition the space to analyze network properties and optimize network layouts.

BSP Complexity and Fragmentation

A key focus of research is minimizing the size of a BSP for different types of objects. The size of a BSP is quantified by the number of fragments it creates from the initial objects. Minimizing fragmentation is crucial because it directly impacts the storage requirements and processing efficiency of the BSP. A smaller BSP size generally leads to faster query times and more efficient rendering or other geometric operations.

Research on Minimizing BSP Size

Significant research has been dedicated to finding BSPs of minimal size for various object types in different dimensions.

Paterson and Yao’s $O(n \log n)$ Result for Disjoint Line Segments

Paterson and Yao made a fundamental contribution by proving that for any set of $n$ disjoint line segments in the plane, a BSP of size $O(n \log n)$ can always be constructed. This result established a crucial upper bound on the BSP size for disjoint line segments and demonstrated the feasibility of efficient space partitioning for this class of objects.

Randomized BSP Construction and Expected Size

Building upon their initial findings, Paterson and Yao further showed that a randomized approach, which involves partitioning space using the supporting lines of the input segments in a random order, achieves the $O(n \log n)$ BSP size in expectation. This randomized algorithm provides a practical method for constructing efficient BSPs and highlights the power of randomization in geometric algorithms.

Special Cases and Object Types

Further research has explored BSP size for segments with:

Segments with Limited Orientations: When line segments have only a constant number of possible orientations (e.g., horizontal and vertical), it’s possible to achieve even smaller BSP sizes, sometimes linear in the number of segments.
Axis-Aligned Rectangles: For sets of axis-aligned rectangles, which are common in many applications, efficient BSP constructions have been developed. Research has aimed to minimize BSP size for both disjoint and overlapping axis-aligned rectangles.
Fat Objects: Fat objects, characterized by a bounded aspect ratio (not excessively elongated or thin), often admit smaller BSPs compared to arbitrarily shaped objects. Linear-size BSPs have been shown to exist for certain classes of fat objects, leading to very efficient spatial data structures.

These special cases exploit specific geometric properties to achieve improved BSP performance and are relevant to particular application domains.

Goal: Asymptotically Optimal $O(n \log n / \log \log n)$ BSP

This lecture aims to delve into the construction of highly efficient BSPs for disjoint line segments in the plane. Our primary goal is to achieve a BSP size of $O(n \log n / \log \log n)$. This bound is significant because it is known to be asymptotically optimal, meaning that it is the best possible size achievable for BSPs of disjoint line segments in the plane, up to a constant factor. We will thoroughly examine the algorithms, data structures, and key geometric concepts and lemmas that underpin this optimal result. Understanding these techniques is crucial for developing efficient spatial partitioning methods in various computational geometry applications.

Preliminaries

BSP Size Measurement: Fragments and Cuts

The size of a BSP is quantified by the total number of fragments it creates from the initial set of line segments. Instead of directly counting these fragments, we adopt a more convenient approach by tracking the number of times a partitioning line intersects, or "cuts," an input segment. Each cut effectively splits a segment into two, thus increasing the fragment count by one. Since we begin with $n$ segments, and each cut adds exactly one fragment, minimizing the total number of cuts is equivalent to minimizing the BSP size. This cut-counting method simplifies the analysis and algorithm design.

Working within Convex Cells

Our BSP construction is a recursive process that operates within convex regions, which we refer to as cells. At each step of building the BSP tree, we maintain a convex cell that encloses all line segments relevant to the current subproblem. The partitioning process refines these cells, creating a hierarchy of convex subdivisions.

Initial Cell $C_0$

The recursion begins with an initial convex cell, denoted as $C_0$, which contains all input line segments. This initial cell can be chosen in several ways:

The entire plane: If the segments are bounded, the entire plane serves as a trivial convex cell.
A bounding box: A tighter initial cell is a bounding box that minimally encloses all input segments. This is often more practical than the entire plane.
The convex hull: The convex hull of all input segments provides the smallest convex region containing all segments, potentially leading to more efficient partitioning.

At each non-leaf node in the BSP tree, a partitioning line is chosen to divide the current cell $C$ into two new convex cells, effectively creating two child cells for the current node. This recursive subdivision continues until each cell contains a sufficiently simple set of segments (or no segments at all).

Segment Types Relative to Cell Boundary $\partial C$

When working with a convex cell $C$ and a set $S$ of disjoint line segments within it, we categorize the segments in $S$ based on the location of their endpoints relative to the boundary $\partial C$ of the cell. This classification is crucial for designing efficient partitioning strategies. We distinguish three types of segments:

Free Segments

Definition 1 (title=Definition: Free Segments, colback=green!20, colframe=green!75!black). A segment $s \in S$ is a free segment if both endpoints of $s$ lie on the boundary $\partial C$ of the convex cell $C$.

Free segments are entirely contained within the boundary of the cell and represent segments that span across the cell.

Boundary Segments

Definition 2 (title=Definition: Boundary Segments, colback=green!20, colframe=green!75!black). A segment $s \in S$ is a boundary segment if exactly one endpoint of $s$ lies on the boundary $\partial C$ (referred to as the outer endpoint), and the other endpoint is located in the interior of $C$ (referred to as the inner endpoint).

Boundary segments have one end anchored on the cell’s boundary and extend into the cell’s interior.

Interior Segments

Definition 3 (title=Definition: Interior Segments, colback=green!20, colframe=green!75!black). A segment $s \in S$ is an interior segment if both endpoints of $s$ are located in the interior of the convex cell $C$.

Interior segments are fully contained within the cell, away from its boundary.

Figure 1 illustrates these three segment types within a convex cell.

Types of line segments in a convex cell.

Prioritizing Free Cuts for Simplification

When constructing a BSP, if free segments are present within the current cell, we prioritize partitioning along their supporting lines. This operation is termed a free cut. Free cuts are particularly advantageous due to two key properties:

No fragmentation increase: Partitioning along a free segment’s supporting line does not create new fragments of the free segment itself, nor of any other segment. The free segment is simply part of the partitioning line.
Problem decomposition: A free cut effectively divides the current problem into two independent subproblems, one in each of the resulting half-spaces. Since the free segment lies on the partitioning line, it does not belong to either of the resulting open half-spaces, leading to strictly smaller subproblems.

To simplify our BSP construction, we adopt a strategy of always performing free cuts whenever possible. This preprocessing step allows us to assume, without loss of generality, that the set of segments $S$ within a cell $C$ consists only of boundary and interior segments, i.e., $S = B \cup I$, where $F = \emptyset$.

SubBSP Algorithm and Lemma 4: Core Partitioning Lemma

The core of our BSP construction relies on the repeated application of a subroutine called SubBSP(B, C, k). This algorithm is formally described by the following crucial lemma, which guarantees certain properties of the binary plane partition it produces.

Lemma 4 (title=Lemma 2.1: Core Partitioning Lemma for SubBSP, colback=red!20, colframe=red!75!black). Let $S$ be a finite set of disjoint line segments in a convex cell $C$, partitioned into boundary segments $B$ and interior segments $I$. For any integer $k$, where $1 \leq k \leq |B|$, there exists a binary plane partition algorithm SubBSP(B,C,k) that satisfies the following conditions:

Bounded boundary segment cuts: Every boundary segment in $B$ is cut at most $O(1)$ times by the partitioning lines generated by SubBSP(B,C,k). This means boundary segments are fragmented a constant number of times.
Controlled interior segment cuts: Every interior segment in $I$ is cut at most $O(k)$ times. The fragmentation of interior segments is controlled by the parameter $k$.
Reduced boundary segment count in subcells: Every cell produced by SubBSP(B,C,k) intersects with fewer than $|B|/k$ segments from the set $B$. This condition ensures that the number of boundary segments is significantly reduced in the subproblems, leading to efficient recursion.

It is important to note that while the input to SubBSP(B, C, k) explicitly includes the set of boundary segments $B$ in cell $C$, the interior segments $I$ are not directly considered as input for this subroutine. Nevertheless, Lemma 4 guarantees a bound on the number of times SubBSP(B, C, k) cuts interior segments. This bound, $O(k)$ cuts per interior segment, arises from the geometric properties of disjointness between interior and boundary segments, as will be detailed in the proof of the lemma.

BSPs Along Conformal Paths

The algorithm SubBSP(B, C, k) leverages a recursive plane partitioning strategy based on conformal paths. Consider a set $B$ of disjoint boundary segments within a convex cell $C$. We begin by directing each boundary segment $b \in B$ from its outer endpoint (on $\partial C$) to its inner endpoint (in the interior of $C$). Let $\vec{b}$ denote the ray originating from the outer endpoint of $b$ and extending along the direction of $b$. Further, let $\bar{b}$ be the directed line segment along $\vec{b}$ starting from the outer endpoint of $b$ and terminating at the first point of intersection with either another boundary segment in $B$ or the boundary $\partial C$.

Directed Boundary Segments and Rays $\vec{b}$, $\bar{b}$

Defining directed boundary segments and the associated rays $\vec{b}$ and segments $\bar{b}$ is a crucial step in constructing conformal paths. These directed entities help establish a consistent directionality and ordering for the partitioning process.

Definition of Conformal Path $\beta$

Definition 5 (title=Definition 2.2: Conformal Path, colback=green!20, colframe=green!75!black). Given a set $B$ of boundary segments in a cell $C$, a simple directed polygonal path $\beta = (u_0, u_1, \ldots, u_t)$ is termed conformal if it satisfies the following two conditions:

Edge alignment: For each edge $\overline{u_{j-1}u_j}$ of the path $\beta$ (where $j = 1, 2, \ldots, t$), there exists a boundary segment $b_j \in B$ such that the directed line segment $\overline{u_{j-1}u_j}$ is contained within $\bar{b}_j$. This means each edge of $\beta$ aligns with the extended portion of some boundary segment.
Disjoint interiors: The portions of the boundary segments $b_j$ between their outer endpoints and the points $u_j$ must have pairwise disjoint relative interiors. This condition ensures that the conformal path follows the boundary segments in a non-overlapping manner.

Conformal paths are essentially polygonal paths that are "glued" together from pieces of extended boundary segments, respecting their directions and disjointness.

ChainBSP Algorithm (Algorithm 6): Partitioning along Conformal Paths

The algorithm ChainBSP($\beta$) provides a method for partitioning space based on a conformal path $\beta$. It partitions the plane sequentially along the supporting lines of the edges of $\beta$, but in reverse order of their appearance in the path.

Algorithm 6 (title=Algorithm 1: ChainBSP($\beta$), colback=blue!20, colframe=blue!75!black). Algorithm 1. ChainBSP($\beta$)

Input: A conformal path $\beta = (u_0, u_1, \ldots, u_t)$ such that for each $j = 1, 2, \ldots, t$, there is a boundary segment $b_j \in B$ with $\overline{u_{j-1}u_j} \subseteq \bar{b}_j$.

For $j = 0, 1, \ldots, t-1$ do:

Partition every cell that intersects the line segment between the outer endpoint of $b_{t-j}$ and point $u_{t-j}$ by the supporting line of $b_{t-j}$.

Complexity Analysis: For a conformal path with $t$ edges, ChainBSP($\beta$) performs $t$ partitioning steps. In each step, partitioning a cell along a line takes time proportional to the number of segments intersecting the cell. A detailed complexity analysis would depend on how segments are managed and updated across partitions, but for now, we focus on the structural properties of the partition.

Proposition 7: Bounded Boundary Segment Cuts in ChainBSP

A key property of ChainBSP($\beta$) is that it limits the fragmentation of boundary segments.

Proposition 7 (title=Proposition 2.3: Bounded Boundary Segment Cuts in ChainBSP, colback=red!20, colframe=red!75!black). For a conformal path $\beta = (u_0, u_1, \ldots, u_t)$, the ChainBSP($\beta$) algorithm cuts every boundary segment at most once. More specifically, only the very first partitioning step in the algorithm, which uses the supporting line of the segment $\overline{u_{t-1}u_t}$ (derived from $b_t$), has the potential to cut boundary segments. Subsequent partitioning steps will not introduce further cuts to boundary segments.

This proposition highlights the efficiency of ChainBSP($\beta$) in controlling the fragmentation of boundary segments.

Interior Segment Cuts in ChainBSP and Need for Simplification

While ChainBSP($\beta$) effectively limits cuts on boundary segments, it may, in its basic form, cut interior segments multiple times. For a conformal path $\beta$ with $t$ edges, an interior segment could potentially be cut up to $t$ times, as each partitioning line in ChainBSP($\beta$) could intersect it. To address this, we will introduce a "simplification" process for conformal paths. We will transform a conformal path $\beta$ into another conformal path $\delta$ such that ChainBSP($\delta$) ensures that every input segment, including interior segments, is cut at most a constant number of times, i.e., $O(1)$ times. This simplification is crucial for achieving the desired BSP size bounds.

Proof of Lemma 4: SubBSP Construction

Let $B$ be a set of $m$ boundary segments in a convex cell $C$, and let $k$ be an integer, $1 \leq k \leq m$. We now detail the construction of SubBSP(B, C, k). The process involves several steps:

Polygonal Paths $\alpha_i$ Construction

We begin by constructing polygonal paths $\alpha_i$. Label the boundary segments as $B = \{s_1, s_2, \ldots, s_m\}$. For each boundary segment $s_i$, we extend it along its direction until it hits another segment, the boundary of $C$, or a previously created extension.

Algorithm ConvexPartition(B) (Algorithm 8): Extended Segments `ext(`$s_i$`)` and $\hat{s}_i$

Algorithm 8 (title=Algorithm 2: ConvexPartition(B), colback=blue!20, colframe=blue!75!black). Algorithm 2. ConvexPartition(B)

For $i = 1$ to $m$, do:

Let ext($s_i$) be the line segment along $\vec{s}_i$ between the inner endpoint of $s_i$ and the first point along $\vec{s}_i$ that lies in $(\bigcup_{j=1}^{i-1} s_j) \cup (\bigcup_{j=1}^{i-1} \text{ext}(s_j)) \cup \partial C$.

Complexity Analysis: The complexity of ConvexPartition(B) is dominated by finding the first intersection point for each segment extension. Using efficient geometric data structures for segment intersection queries, this can be done in $O(m \log m)$ time for all $m$ segments.

Let $\hat{s}_i = s_i \cup \text{ext}(s_i)$ be the extended segment. The relative interiors of the extended segments $\hat{s}_i$ are pairwise disjoint. For each $s_i \in B$, we construct a path $\alpha_i$ that follows the directions of the extended segments.

Algorithm PathBuilder(i, R) (Algorithm 9): Constructing Paths $\alpha_i$

Algorithm 9 (title=Algorithm 3: PathBuilder(i, R), colback=blue!20, colframe=blue!75!black). Algorithm 3. PathBuilder(i, R)

Let the first vertex of $\alpha_i$ be the outer endpoint of $s_i$, and let $s := \hat{s}_i$.

Until the head of $s$ lies along $\partial C$ or in the relative interior of a previous edge of $\alpha_i$.

Append the head of segment $s$ to $\alpha_i$.
Let $b \in B$ be the boundary segment such that the head of $s$ lies in the relative interior of $\hat{b}$, and set $s := \hat{b}$.

Complexity Analysis: The PathBuilder algorithm constructs each path $\alpha_i$ by traversing extended segments. In the worst case, a path might visit a significant portion of the arrangement of extended segments. However, since the number of boundary segments is $m$, and each extension is computed efficiently, the complexity of building all paths $\alpha_i$ for all $i$ from 1 to $m$ is bounded by $O(m^2)$ in a naive implementation, but can be optimized to $O(m \log m)$ with efficient spatial data structures.

Figure 2 illustrates the construction of these paths.

Paths $\alpha_i$, Conformal Paths, and Convex Cycles $\varphi_i$

Proposition 10 (title=Proposition 3.1: Paths $\alpha_i$ Decomposition, colback=red!20, colframe=red!75!black). If a path $\alpha_i$, $1 \leq i \leq m$, terminates at a point $q$ in the interior of $C$, then $\alpha_i$ is composed of a conformal path $\alpha'_i$ from the outer endpoint of $s_i$ to $q$, and a directed convex cycle $\varphi_i$.

Let $R_i = \bigcup \{s_j : \alpha_i \cap \hat{s}_j \neq \emptyset\}$ be the union of extended boundary segments visited by path $\alpha_i$. The cycle $\varphi_i$ is the boundary of one of the convex faces formed by $R_i$.

Proposition on Intersection of Paths $\alpha_i$ and $\alpha_j$ and Common Cycles

Proposition 11 (title=Proposition 3.2: Intersection of Paths and Common Cycles, colback=red!20, colframe=red!75!black). For every $1 \leq i < j \leq m$, if paths $\alpha_i$ and $\alpha_j$ intersect, then $\varphi_i = \varphi_j$.

Proposition on Ray Crossing Subpaths $\psi$ of $\alpha_i$

Proposition 12 (title=Proposition 3.3: Ray Crossing Subpaths, colback=red!20, colframe=red!75!black). Let $\psi = (u_0, u_1, \ldots, u_t)$ be a subpath of $\alpha'_i$ for some $1 \leq i \leq m$. Then the ray $\overrightarrow{u_{t-1}u_t}$ cannot cross path $\psi$.

Selecting Paths and Constructing Dual Graph $G_P$

Let $R = \bigcup_{i=1}^m \alpha_i$ be the union of all paths. For any subset $P \subseteq \{1, 2, \ldots, m\}$, let $R_P = \bigcup_{i \in P} \alpha_i$. $R_P$ decomposes $C$ into faces $F_P$. We define a dual graph $G_P$ where nodes are faces in $F_P$, and adjacency is defined by sharing a boundary segment’s outer endpoint.

Set of Paths $R_P = \bigcup_{i \in P} \alpha_i$ and Faces $F_P$

The set $R_P$ is formed by taking the union of the polygonal paths $\alpha_i$ for all indices $i$ in the chosen subset $P$. This set of paths $R_P$ acts as a planar subdivision within the convex cell $C$. The faces $F_P$ are then the connected components of the region obtained by removing $R_P$ from $C$, i.e., $F_P = C \setminus R_P$. These faces are convex polygons or unbounded convex regions.

Dual Graph $G_P$ Definition: Faces as Nodes

Definition 13 (title=Definition 3.4: Dual Graph $G_P$, colback=green!20, colframe=green!75!black). The dual graph $G_P$ is a graph where each node represents a face in $F_P$. Two nodes in $G_P$ are adjacent if and only if their corresponding faces in $F_P$ are adjacent along the boundary, specifically if they are both incident to a common outer endpoint of some boundary segment $s_i$, where $i \in P$.

Algorithm PathSelector(B, C, k) (Algorithm 14): Selecting Paths to Control Face Complexity

Algorithm 14 (title=Algorithm 4: PathSelector(B, C, k), colback=blue!20, colframe=blue!75!black). Algorithm 4. PathSelector(B, C, k)

Let $P := \{1, 2, \ldots, m\}$.

For $i =1$ to $m$, do:

If the faces of $F_P$ incident to the outer endpoint of $s_i$ jointly intersect at most $m/(2k) - 2$ boundary segments, then let $P := P \setminus \{i\}$.

Output $P$.

Complexity Analysis: The PathSelector algorithm iterates through each boundary segment $s_i$. In each iteration, it needs to check the number of boundary segments intersected by the faces incident to the outer endpoint of $s_i$. This requires traversing the faces of the arrangement $F_P$ and counting segment intersections, which can be done in time related to the complexity of the arrangement. A detailed analysis would depend on the data structure used to represent $F_P$, but a reasonable implementation can achieve a runtime of $O(m^2)$ for the entire PathSelector algorithm, and with optimization, potentially closer to $O(m \log m)$.

Proposition 15: Boundary Segment Intersections per Face after Path Selection

Proposition 15 (title=Proposition 3.5: Boundary Segment Intersections after Path Selection, colback=red!20, colframe=red!75!black). Let $P = \texttt{PathSelector(B, C, k)}$.

Every face $f \in F_P$ intersects at most $m/(2k) - 1$ boundary segments.
If $f_1, f_2 \in F_P$, $f_1 \neq f_2$, are adjacent along the boundary, then they jointly intersect at least $m/(2k) - 1$ boundary segments.

Dual Graph of Connected Components $H_P$

Nodes: Connected Components of $R_P$

In addition to the dual graph $G_P$ on faces, we define another dual graph $H_P$ that captures the connectivity of the components of $R_P$. The nodes of $H_P$ correspond to the connected components of the path diagram $R_P = \bigcup_{i \in P} \alpha_i$.

Edges: Adjacency through Faces in $F_P$

Two nodes in $H_P$ are connected by an edge if and only if their corresponding connected components in $R_P$ are adjacent to the same face in the face subdivision $F_P$. Adjacency here means that the components and the face share a boundary.

Tree Structure of $H_P$

A crucial property of the dual graph $H_P$ is that it is always a tree. This tree structure reflects the hierarchical and non-cyclic nature of how the connected components of $R_P$ decompose the convex cell $C$. The tree structure of $H_P$ is essential for the recursive partitioning strategy used in the SubBSP algorithm.

Figure 3 illustrates the dual graph of connected components.

Lemma 16: Bounding Paths within Connected Components of $H_P$

Lemma 16 (title=Lemma 3.6: Bounding Paths in Connected Components, colback=red!20, colframe=red!75!black). Let $P = \texttt{PathSelector(B,C,k)}$, and let $Q_1, Q_2, \ldots, Q_l$ be connected components of $R_P$ corresponding to a simple path in $H_P$. Then $Q_1, Q_2, \ldots, Q_l$ jointly contain at most $10k$ paths $\alpha_i$, $i \in P$.

Proof of Lemma 16: [Proof content will be added here based on the transcript and geometric reasoning. This is a placeholder for the detailed proof.]

Reduction to Single Component: Sectors $C'$ and Components $R'_P$

The diagram $R_P = \bigcup_{i \in P} \alpha_i$ may consist of several connected components. To simplify the partitioning process, we aim to separate these components and reduce the problem to handling a single connected component at a time. Recall that each connected component of $R_P$ lies within a unique sector of the cell $C$. These sectors are formed by partitioning $C$ using chords.

Lemma 17 and Algorithm SubBSP

Lemma 17 (title=Lemma 3.7: Properties of CompBSP, colback=red!20, colframe=red!75!black). Let $R'_P$ be a connected component of $R_P$ containing $h \in \mathbb{N}$ paths $\alpha_i$. Let $C' \subseteq C$ be the sector of $C$ containing $R'_P$. There exists a BSP algorithm CompBSP(B,C’, R’p) such that:

Every boundary segment in $C'$ is cut $O(1)$ times.
Every interior segment is cut at most $O(h)$ times.
Every cell produced by CompBSP(B,C’, R’p) intersects less than $m/k$ boundary segments.

Algorithm SubBSP(B, C, k) (Algorithm 18): Recursive Partitioning Strategy

Algorithm 18 (title=Algorithm 5: SubBSP(B, C, k), colback=blue!20, colframe=blue!75!black). Algorithm 5. SubBSP(B, C, k)

Sector Partitioning: For every non-leaf component $R'_P \subseteq R_P$ in the dual graph $H_P$, partition the cell $C$ along the chord $e(R'_P)$ associated with that component. This step divides $C$ into sectors, each containing a single connected component of $R_P$.
Component Processing: For each connected component $R'_P \subseteq R_P$ and its corresponding sector $C'$, recursively call CompBSP(B, C’, R’p) to further partition within each sector.

Complexity Analysis: The complexity of SubBSP(B, C, k) is dominated by the calls to CompBSP and the initial partitioning along chords. If there are $l$ connected components, and the complexity of CompBSP is $T_{CompBSP}$, the complexity of SubBSP is roughly $O(m \log m + l \cdot T_{CompBSP})$, where $O(m \log m)$ accounts for path selection and dual graph construction.

Processing a Single Component $R'_P$

Now we focus on processing a single connected component $R'_P$ of $R_P$ within its sector $C'$. Let $R'$ be the component of $R$ that contains $R'_P$. We decompose $R'_P$ into a set of non-overlapping conformal paths $\Gamma = \{\beta_1, \beta_2, \ldots, \beta_g\}$. This decomposition allows us to apply ChainBSP in a structured way.

Path Simplification: Algorithm Simplify

Algorithm Simplify(B,C,$\gamma$) (Algorithm 19): Simplifying Convex Conformal Paths

Algorithm 19 (title=Algorithm 6: Simplify(B,C,$\gamma$), colback=blue!20, colframe=blue!75!black). Algorithm 6. Simplify(B,C,$\gamma$)

Input: A set $B$ of boundary segments in a convex cell $C$, and a convex conformal path $\gamma = (u_e, u_{e+1}, \ldots, u_t)$ which makes right turns only.

Set $\delta := \gamma$.

While $\delta$ has four consecutive vertices $(a_0, a_1, a_2, a_3)$ such that there are boundary segments $b_1, b_3 \in B$ with $\overline{a_0a_1} \subseteq b_1$ and $\overline{a_2a_3} \subseteq b_3$; and the intersection point $x$ of the supporting line of $b_1$ and $b_3$ lies in the part of $b_3$ between the outer endpoint of $b_3$ and $a_2$, do:

Replace the subpath $(a_0, a_1, a_2, a_3)$ by $(a_0, x, a_3)$ in $\delta$.

Output: $\delta$.

Complexity Analysis: The Simplify algorithm iteratively reduces the number of vertices in the conformal path $\gamma$. In each iteration, it computes the intersection of two lines and checks a geometric condition. The number of vertices is reduced in each step, and the overall number of vertices in $\gamma$ is at most $m$. Thus, the complexity of Simplify is bounded by $O(m^2)$ in a naive implementation, but can be optimized to be more efficient with careful implementation of intersection checks and path updates.

Proposition 20: Interior Segment Cuts after Simplification: $O(1)$ Cuts

Proposition 20 (title=Proposition 3.8: Interior Segment Cuts after Simplification, colback=red!20, colframe=red!75!black). If $\gamma$ is a convex conformal path and $\delta = \texttt{Simplify(B,C,$$)}$, then ChainBSP($\delta$) cuts every interior segment $O(1)$ times.

Proof of Lemma 17 and Algorithm CompBSP

Algorithm CompBSP(B,C’, R’p) (Algorithm 21): Processing a Component using Simplified Paths

Algorithm 21 (title=Algorithm 7: CompBSP(B,C’, R’p), colback=blue!20, colframe=blue!75!black). Algorithm 7. CompBSP(B,C’, R’p)

Input: Boundary segments $B$ in cell $C'$, and a connected component $R'_P \subseteq R_P$. Decompose $R'_P$ into non-overlapping conformal paths $\Gamma = \{\beta_1, \beta_2, \ldots, \beta_g\}$. Let $\delta_i = \texttt{Simplify}(B,C',\gamma_i)$ for each $\gamma_i \in \Gamma$.

For $i = 1, 2, \ldots, g$, do:

Apply ChainBSP($\delta_i$).

Complexity Analysis: The CompBSP algorithm iterates through the simplified conformal paths $\delta_i$. For each path, it calls ChainBSP. If there are $g$ paths and the maximum length of a simplified path is $z$, and assuming ChainBSP on a path of length $z$ takes $O(z \cdot m')$ time where $m'$ is the number of segments in the current cell, the total complexity of CompBSP would be roughly $O(\sum_{i=1}^g |\delta_i| \cdot |B|)$. Since the total number of edges in all $\delta_i$ is related to the number of paths $h$ in $R'_P$, and simplification reduces path complexity, a reasonable bound for CompBSP is achievable within $O(h \cdot |B|)$ or $O(h \cdot m \log m)$ with efficient implementations.

Proposition 22: Face Intersections: Bounding Remaining Boundary Segments

Proposition 22 (title=Proposition 3.9: Face Intersections in CompBSP, colback=red!20, colframe=red!75!black). Every (open) face $f \in F'_P$ produced by CompBSP(B,C’, R’p) intersects at most $m/(2k) - 1$ boundary segments.

Proof of Theorem [theorem:optimal_bsp_size]: Optimal BSP Size

Recursive BSP Algorithm (Algorithm 23)

Algorithm BSP(S, C, k) (Algorithm 23): Top-Level BSP Construction

Algorithm 23 (title=Algorithm 8: BSP(S, C, k), colback=blue!20, colframe=blue!75!black). Algorithm 8. BSP(S, C, k)

Boundary Segment Check: If the set of boundary segments $B$ in the current cell $C$ is not empty (i.e., $|B| > 0$), proceed with subdivision. Otherwise, if $|B| = 0$, and there are still segments in $S$ within $C$, partition along an arbitrary segment.
Subproblem Call: If $|B| > 0$, call SubBSP(B, C, min(|B|,k)). The parameter $k$ is capped at $|B|$ to avoid exceeding the number of boundary segments. If $|B| = 0$ and $S$ is not empty, partition $C$ along the supporting line of an arbitrary segment $s \in S$.
Recursive Calls: For each cell $C'$ produced in step 1 that still contains segments (i.e., $S(C') \neq \emptyset$), recursively call BSP(C’, S(C’), k) to continue the partitioning process in the subcells.

Complexity Analysis: The overall runtime of BSP(S, C, k) depends on the depth of recursion and the complexity of SubBSP. With $k = \lceil \frac{\log n}{\log \log n} \rceil$, and given the properties of SubBSP, the algorithm achieves a total runtime of $O(n \log^3 n / \log \log n)$, as discussed in Section 5.5.

Lemma 24: BSP Size of $O(n \log n / \log \log n)$

Lemma 24 (title=Lemma 4.1: Optimal BSP Size, colback=red!20, colframe=red!75!black). For a set $S_0$ of $n$ disjoint line segments in a convex cell $C_0$, BSP$(S_0, C_0, \lceil \frac{\log n}{\log \log n} \rceil)$ is a BSP for $S$, and it partitions $S$ into $O(n \log n / \log \log n)$ fragments.

Proof of Lemma 24: [Proof content will be added here based on the charging scheme and recursive analysis described in the transcript. This is a placeholder for the detailed proof.]

Auto-partitions for Disjoint Line Segments

Adapting ChainBSP for Auto-partitions

We adjust the BSP algorithm to obtain an auto-partition of size $O(n \log n / \log \log n)$. We use ChainBSP($\delta$) as a building block, ensuring the paths $\delta$ satisfy conditions for auto-partitioning.

Proposition 25: Conditions for ChainBSP to be an Auto-partition

Proposition 25 (title=Proposition 5.1: ChainBSP as Auto-partition, colback=red!20, colframe=red!75!black). Let $\delta = (v_0, v_1, \ldots, v_z)$ be a convex conformal path. Assume that $\delta$ and the boundary segments $b_j$ with $\overline{v_{j-1}v_j} \subseteq b_j$, for $j = 1, 2, \ldots, z$, lie in a single cell. ChainBSP($\delta$) is an auto-partition if the supporting line of $b_z$ does not cross the part of $b_1$ between the outer endpoint of $b_1$ and point $v_1$.

Proposition 26: Conditions for Simplified ChainBSP to be an Auto-partition

Proposition 26 (title=Proposition 5.2: Simplified ChainBSP as Auto-partition, colback=red!20, colframe=red!75!black). *Let $\gamma_i \in \Gamma$, and $\delta_i = \texttt{Simplify(B,C,$_i$)}$. Assume that $\delta_i = (v_0, v_1, \ldots, v_z)$ and the boundary segments $b_j$ with $\overline{v_{j-1}v_j} \subseteq b_j$, for $j = 1, 2, \ldots, z$, lie in a single cell. ChainBSP($\delta_i$) is an auto-partition if*

$\gamma_i$ is not part of the convex cycle $\varphi$, or
$\gamma_i$ is part of the convex cycle $\varphi$ but the turning angle of $\gamma_i$ at most $180^\circ$.

Lemma 27: SubAuto Algorithm and Properties

Lemma 27 (title=Lemma 5.3: Properties of SubAuto, colback=red!20, colframe=red!75!black). Let $S$ be a finite set of disjoint line segments in the plane. For every integer $k$, $1 \leq k \leq |B|$, there is an auto-partition SubAuto(B,C,k) such that

Every boundary segment in $B$ is cut at most $O(1)$ times on average;
Every interior segment in $I$ is cut at most $O(k)$ times;
Every cell produced by SubAuto(B,C,k) intersects at most $|B|/k$ segments in $B$.

Construction of a BSP in O(n polylog n) Time

[Content about the construction time will be added here.]

Conclusion

[Conclusion content will be added here.]

Exercises

[Exercises content will be added here.]

References

P. K. Agarwal, E. F. Grove, T. M. Murali, and J. S. Vitter, Binary space partitions for fat rectangles, SIAM J. Comput. 29 (2000), 1422-1448. S. Ar, B. Chazelle, and A. Tal, Self-customized BSP trees for collision detection, Comput. Geom. Theory Appl. 15 (1-3) (2000), 91–102. S. Ar, G. Montag, and A. Tal, Deferred, self-organizing BSP trees, Comput. Graph. Forum 21 (3) (2002), 269–278. S. Arya, Binary space partitions for axis-parallel line segments: size-height tradeoffs, Inform. Proc. Letts. 84 (4) (2002), 201-206. S. Arya, T. Malamatos, and D.M. Mount, Nearly optimal expected-case planar point location, in Proc. 41st Sympos. Foundations of Comp. Sci., IEEE Press, 2000, pp. 208–218. T. Asano, M. de Berg, O. Cheong, L.J. Guibas, J. Snoeyink, and H. Tamaki, Spanning trees crossing few barriers, Discrete Comput. Geom. 30 (2003), 591–606. M. de Berg, Linear size binary space partitions for fat objects, in Proc. 3rd European Sympos. Algorithms, vol. 979 of LNCS, Springer, Berlin, 1995, pp. 252-263. M. de Berg, Linear size binary space partitions for uncluttered scenes, Algorithmica 28 (3) (2000), 353-366. M. de Berg, H. David, M. Katz, M. Overmars, A.F. van der Stappen, and J. Vleugels, Guarding scenes against invasive hypercubes, Comput. Geom. Theory Appl. 26 (2003), 99–117. M. de Berg, M. de Groot, and M. Overmars, New results on binary space partitions in the plane, Comput. Geom. Theory Appl. 8 (1997), 317-333. M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, Computational Geometry: Algorithms and Applications, 3rd edition, Springer, Berlin, 2008. M. de Berg and M. Streppel, Approximate range searching using binary space partitions, Comput. Geom. Theory Appl. 33 (3) (2006), 139–151. B. Chazelle, H. Edelsbrunner, M. Grigni, L. J. Guibas, J. Hershberger, M. Sharir, and J. Snoeyink, Ray shooting in polygons using geodesic triangulations, Algorithmica 12 (1994), 54-68. N. Chin and S. Feiner, Fast object-precision shadow generation for areal light sources using BSP trees, Comput. Graph. 25 (1992), 21-30. A. Dumitrescu, J. S. B. Mitchell, and M. Sharir, Binary space partitions for axis-parallel segments, rectangles, and hyperrectangles, Discrete Comput. Geom. 31 (2) (2004), 207–227. H. Fuchs, Z. M. Kedem, and B. Naylor, On visible surface generation by a priori tree structures, Comput. Graph. 14 (3) (1980), 124–133. Proc. SIGGRAPH. J. Hershberger and S. Suri, A pedestrian approach to ray shooting: Shoot a ray, take a walk, J. Algorithms 18 (3) (1995), 403-431. J. Hershberger, S. Suri and Cs. D. Tóth, Binary space partitions of orthogonal subdivisions, SIAM J. Comput. 34 (6) (2005), 1380–1397. M. Ishaque, B. Speckmann, and Cs. D. Tóth, Shooting permanent rays among disjoint polygons in the plane, in Proc. 25th ACM Sympos. Comput. Geom. ACM Press, 2009, these proceedings. C.S. Mata and J.S.B. Mitchell, Approximation algorithms for geometric tour and network design problems, in Proc. 11th ACM Sympos. Comput. Geom. ACM Press, 1995, pp. 360–369. B. Naylor, Constructing good partitioning trees, Proc. Graphics Interface, 1993, Canadian Human-Computer Communications Society, Toronto, pp. 181–191. M. S. Paterson and F. F. Yao, Efficient binary space partitions for hidden-surface removal and solid modeling, Discrete Comput. Geom. 5 (1990), 485–503. M. S. Paterson and F. F. Yao, Optimal binary space partitions for orthogonal objects, J. Algorithms 13 (1992), 99–113. R. A. Schumacker, R. Brand, M. Gilliland, and W. Sharp, Study for applying computer generated images to visual simulation, Tech. Rep. AFHRL–TR–69–14, San Antonio, TX, 1969. W. C. Thibault and B. F. Naylor, Set operations on polyhedra using binary space partitioning trees, Comput. Graph. 21 (4) (1987), 153–162, Proc. SIGGRAPH ’87. Cs. D. Tóth, A note on binary plane partitions, Discrete Comput. Geom. 30 (2003), 3–16. Cs. D. Tóth, Binary space partition for axis-aligned fat rectangles, SIAM J. Comput. 38 (1) (2008), 429–447. Cs. D. Tóth, Binary space partition for line segments with a limited number of directions, SIAM J. Comput. 32 (2) (2003), 307–325.

--- title: "Binary Space Partitions for Disjoint Line Segments" author: "Your Name" date: "2025-02-08" format: html: toc: true # Table of Contents toc-depth: 2 code-tools: true theme: cosmo # Or "journal" for Distill-like minimalism --- # Introduction {#sec:introduction} ## Binary Space Partition (BSP) Definition {#subsec:bsp_definition} A binary space partition (BSP) is a hierarchical method for decomposing space. It recursively divides space, and objects within it, using hyperplanes. This process continues, clipping objects against these hyperplanes and recursing within the resulting half-spaces. The complexity of a BSP is measured by the number of fragments created from the initial objects. This lecture explores binary space partitions for sets of disjoint line segments in the plane, aiming to construct BSPs of minimal size. ## Applications of BSPs {#subsec:bsp_applications} BSPs were initially developed in computer graphics to manage the rendering order of objects, particularly for hidden surface removal and z-buffering. Their simplicity and efficiency have led to applications in various fields. ### Computer Graphics: Hidden Surface Removal and Z-buffering {#subsubsection:graphics_applications} In computer graphics, BSPs are instrumental in resolving the hidden surface problem. By constructing a BSP, polygons in a 3D scene can be ordered from back to front, allowing for efficient rendering by drawing only the visible surfaces. This ordering also facilitates z-buffering, a technique used to determine the visibility of objects pixel by pixel. ### Solid Modeling {#subsubsection:solid_modeling_applications} BSPs are used in solid modeling to represent and manipulate 3D shapes. They provide a way to decompose complex shapes into simpler convex regions, which is useful for operations like set operations (union, intersection, difference) and point-in-solid tests. ### Shadow Generation {#subsubsection:shadow_generation_applications} Generating shadows efficiently in computer graphics is another application of BSPs. By using BSPs, it's possible to determine which surfaces are occluded from a light source and thus should be in shadow. BSPs can be used to create shadow volumes or shadow maps for realistic shadow rendering. ### Motion Planning {#subsubsection:motion_planning_applications} In robotics and virtual environments, motion planning involves finding a path for a robot or agent to move from one location to another without colliding with obstacles. BSPs can represent the environment and the obstacles, allowing for efficient path planning algorithms by searching through the BSP space. ### Range Searching {#subsubsection:range_searching_applications} BSPs can be adapted for range searching in spatial databases. Given a set of points or objects in space, range searching involves finding all objects within a specified query region. BSPs can accelerate range queries by quickly pruning parts of the space that do not intersect the query region. ### Network Design {#subsubsection:network_design_applications} In network design, particularly in wireless and sensor networks, BSPs can be used to solve geometric optimization problems. For example, in coverage problems or interference analysis, BSPs can help partition the space to analyze network properties and optimize network layouts. ## BSP Complexity and Fragmentation {#subsec:bsp_complexity} A key focus of research is minimizing the size of a BSP for different types of objects. The size of a BSP is quantified by the number of fragments it creates from the initial objects. Minimizing fragmentation is crucial because it directly impacts the storage requirements and processing efficiency of the BSP. A smaller BSP size generally leads to faster query times and more efficient rendering or other geometric operations. ## Research on Minimizing BSP Size {#subsec:research_bsp_size} Significant research has been dedicated to finding BSPs of minimal size for various object types in different dimensions. ### Paterson and Yao's $O(n \log n)$ Result for Disjoint Line Segments {#subsubsection:paterson_yao_result} Paterson and Yao made a fundamental contribution by proving that for any set of $n$ disjoint line segments in the plane, a BSP of size $O(n \log n)$ can always be constructed. This result established a crucial upper bound on the BSP size for disjoint line segments and demonstrated the feasibility of efficient space partitioning for this class of objects. ### Randomized BSP Construction and Expected Size {#subsubsection:randomized_bsp} Building upon their initial findings, Paterson and Yao further showed that a randomized approach, which involves partitioning space using the supporting lines of the input segments in a random order, achieves the $O(n \log n)$ BSP size in expectation. This randomized algorithm provides a practical method for constructing efficient BSPs and highlights the power of randomization in geometric algorithms. ### Special Cases and Object Types {#subsubsection:special_cases_bsp} Further research has explored BSP size for segments with: - **Segments with Limited Orientations:** When line segments have only a constant number of possible orientations (e.g., horizontal and vertical), it's possible to achieve even smaller BSP sizes, sometimes linear in the number of segments. - **Axis-Aligned Rectangles:** For sets of axis-aligned rectangles, which are common in many applications, efficient BSP constructions have been developed. Research has aimed to minimize BSP size for both disjoint and overlapping axis-aligned rectangles. - **Fat Objects:** Fat objects, characterized by a bounded aspect ratio (not excessively elongated or thin), often admit smaller BSPs compared to arbitrarily shaped objects. Linear-size BSPs have been shown to exist for certain classes of fat objects, leading to very efficient spatial data structures. These special cases exploit specific geometric properties to achieve improved BSP performance and are relevant to particular application domains. ## Goal: Asymptotically Optimal $O(n \log n / \log \log n)$ BSP {#subsec:optimal_bsp_goal} This lecture aims to delve into the construction of highly efficient BSPs for disjoint line segments in the plane. Our primary goal is to achieve a BSP size of $O(n \log n / \log \log n)$. This bound is significant because it is known to be asymptotically optimal, meaning that it is the best possible size achievable for BSPs of disjoint line segments in the plane, up to a constant factor. We will thoroughly examine the algorithms, data structures, and key geometric concepts and lemmas that underpin this optimal result. Understanding these techniques is crucial for developing efficient spatial partitioning methods in various computational geometry applications. # Preliminaries {#sec:preliminaries} ## BSP Size Measurement: Fragments and Cuts {#subsec:bsp_size_measurement} The size of a BSP is quantified by the total number of fragments it creates from the initial set of line segments. Instead of directly counting these fragments, we adopt a more convenient approach by tracking the number of times a partitioning line intersects, or \"cuts,\" an input segment. Each cut effectively splits a segment into two, thus increasing the fragment count by one. Since we begin with $n$ segments, and each cut adds exactly one fragment, minimizing the total number of cuts is equivalent to minimizing the BSP size. This cut-counting method simplifies the analysis and algorithm design. ## Working within Convex Cells {#subsec:convex_cells} Our BSP construction is a recursive process that operates within convex regions, which we refer to as **cells**. At each step of building the BSP tree, we maintain a convex cell that encloses all line segments relevant to the current subproblem. The partitioning process refines these cells, creating a hierarchy of convex subdivisions. ### Initial Cell $C_0$ {#subsubsection:initial_cell} The recursion begins with an initial convex cell, denoted as $C_0$, which contains all input line segments. This initial cell can be chosen in several ways: - **The entire plane:** If the segments are bounded, the entire plane serves as a trivial convex cell. - **A bounding box:** A tighter initial cell is a bounding box that minimally encloses all input segments. This is often more practical than the entire plane. - **The convex hull:** The convex hull of all input segments provides the smallest convex region containing all segments, potentially leading to more efficient partitioning. At each non-leaf node in the BSP tree, a partitioning line is chosen to divide the current cell $C$ into two new convex cells, effectively creating two child cells for the current node. This recursive subdivision continues until each cell contains a sufficiently simple set of segments (or no segments at all). ## Segment Types Relative to Cell Boundary $\partial C$ {#subsec:segment_types} When working with a convex cell $C$ and a set $S$ of disjoint line segments within it, we categorize the segments in $S$ based on the location of their endpoints relative to the boundary $\partial C$ of the cell. This classification is crucial for designing efficient partitioning strategies. We distinguish three types of segments: ### Free Segments {#subsubsection:free_segments} ::: definition **Definition 1** (title=Definition: Free Segments, colback=green!20, colframe=green!75!black). A segment $s \in S$ is a **free segment** if both endpoints of $s$ lie on the boundary $\partial C$ of the convex cell $C$. ::: Free segments are entirely contained within the boundary of the cell and represent segments that span across the cell. ### Boundary Segments {#subsubsection:boundary_segments} ::: definition **Definition 2** (title=Definition: Boundary Segments, colback=green!20, colframe=green!75!black). A segment $s \in S$ is a **boundary segment** if exactly one endpoint of $s$ lies on the boundary $\partial C$ (referred to as the **outer endpoint**), and the other endpoint is located in the interior of $C$ (referred to as the **inner endpoint**). ::: Boundary segments have one end anchored on the cell's boundary and extend into the cell's interior. ### Interior Segments {#subsubsection:interior_segments} ::: definition **Definition 3** (title=Definition: Interior Segments, colback=green!20, colframe=green!75!black). A segment $s \in S$ is an **interior segment** if both endpoints of $s$ are located in the interior of the convex cell $C$. ::: Interior segments are fully contained within the cell, away from its boundary. **Figure [1](#fig:segment_types){reference-type="ref" reference="fig:segment_types"}** illustrates these three segment types within a convex cell. <figure id="fig:segment_types"> <table> <tbody> <tr> <td style="text-align: center;"><img src="example-image-a" style="width:45.0%" alt="image" /></td> <td style="text-align: center;"><img src="example-image-b" style="width:45.0%" alt="image" /></td> </tr> <tr> <td style="text-align: center;">(a) Free segments</td> <td style="text-align: center;">(b) Boundary segments</td> </tr> <tr> <td style="text-align: center;"><img src="example-image-a" style="width:45.0%" alt="image" /></td> <td style="text-align: center;"><img src="example-image-b" style="width:45.0%" alt="image" /></td> </tr> <tr> <td style="text-align: center;">(c) Boundary segments in <span class="math inline">$C_2$</span></td> <td style="text-align: center;">(d) Interior segments in <span class="math inline">$C_2$</span></td> </tr> </tbody> </table> <figcaption>Types of line segments in a convex cell.</figcaption> </figure> ## Prioritizing Free Cuts for Simplification {#subsec:free_cuts} When constructing a BSP, if free segments are present within the current cell, we prioritize partitioning along their supporting lines. This operation is termed a **free cut**. Free cuts are particularly advantageous due to two key properties: - **No fragmentation increase:** Partitioning along a free segment's supporting line does not create new fragments of the free segment itself, nor of any other segment. The free segment is simply part of the partitioning line. - **Problem decomposition:** A free cut effectively divides the current problem into two independent subproblems, one in each of the resulting half-spaces. Since the free segment lies on the partitioning line, it does not belong to either of the resulting open half-spaces, leading to strictly smaller subproblems. To simplify our BSP construction, we adopt a strategy of always performing free cuts whenever possible. This preprocessing step allows us to assume, without loss of generality, that the set of segments $S$ within a cell $C$ consists only of boundary and interior segments, i.e., $S = B \cup I$, where $F = \emptyset$. ## SubBSP Algorithm and Lemma [4](#lemma:subbsp_core_lemma){reference-type="ref" reference="lemma:subbsp_core_lemma"}: Core Partitioning Lemma {#subsec:subbsp_lemma3} The core of our BSP construction relies on the repeated application of a subroutine called `SubBSP(B, C, k)`. This algorithm is formally described by the following crucial lemma, which guarantees certain properties of the binary plane partition it produces. ::: {.lemma:subbsp_core_lemma .lemma} **Lemma 4** (title=Lemma 2.1: Core Partitioning Lemma for SubBSP, colback=red!20, colframe=red!75!black). *Let $S$ be a finite set of disjoint line segments in a convex cell $C$, partitioned into boundary segments $B$ and interior segments $I$. For any integer $k$, where $1 \leq k \leq |B|$, there exists a binary plane partition algorithm `SubBSP(B,C,k)` that satisfies the following conditions:* 1. ***Bounded boundary segment cuts:** Every boundary segment in $B$ is cut at most $O(1)$ times by the partitioning lines generated by `SubBSP(B,C,k)`. This means boundary segments are fragmented a constant number of times.* 2. ***Controlled interior segment cuts:** Every interior segment in $I$ is cut at most $O(k)$ times. The fragmentation of interior segments is controlled by the parameter $k$.* 3. ***Reduced boundary segment count in subcells:** Every cell produced by `SubBSP(B,C,k)` intersects with fewer than $|B|/k$ segments from the set $B$. This condition ensures that the number of boundary segments is significantly reduced in the subproblems, leading to efficient recursion.* ::: It is important to note that while the input to `SubBSP(B, C, k)` explicitly includes the set of boundary segments $B$ in cell $C$, the interior segments $I$ are not directly considered as input for this subroutine. Nevertheless, Lemma [4](#lemma:subbsp_core_lemma){reference-type="ref" reference="lemma:subbsp_core_lemma"} guarantees a bound on the number of times `SubBSP(B, C, k)` cuts interior segments. This bound, $O(k)$ cuts per interior segment, arises from the geometric properties of disjointness between interior and boundary segments, as will be detailed in the proof of the lemma. ## BSPs Along Conformal Paths {#subsec:bsps_conformal_paths} The algorithm `SubBSP(B, C, k)` leverages a recursive plane partitioning strategy based on **conformal paths**. Consider a set $B$ of disjoint boundary segments within a convex cell $C$. We begin by directing each boundary segment $b \in B$ from its outer endpoint (on $\partial C$) to its inner endpoint (in the interior of $C$). Let $\vec{b}$ denote the ray originating from the outer endpoint of $b$ and extending along the direction of $b$. Further, let $\bar{b}$ be the directed line segment along $\vec{b}$ starting from the outer endpoint of $b$ and terminating at the first point of intersection with either another boundary segment in $B$ or the boundary $\partial C$. ### Directed Boundary Segments and Rays $\vec{b}$, $\bar{b}$ {#subsubsection:directed_segments_rays} Defining directed boundary segments and the associated rays $\vec{b}$ and segments $\bar{b}$ is a crucial step in constructing conformal paths. These directed entities help establish a consistent directionality and ordering for the partitioning process. ### Definition of Conformal Path $\beta$ {#subsubsection:conformal_path_definition} ::: {.def:conformal_path .definition} **Definition 5** (title=Definition 2.2: Conformal Path, colback=green!20, colframe=green!75!black). Given a set $B$ of boundary segments in a cell $C$, a simple directed polygonal path $\beta = (u_0, u_1, \ldots, u_t)$ is termed **conformal** if it satisfies the following two conditions: 1. **Edge alignment:** For each edge $\overline{u_{j-1}u_j}$ of the path $\beta$ (where $j = 1, 2, \ldots, t$), there exists a boundary segment $b_j \in B$ such that the directed line segment $\overline{u_{j-1}u_j}$ is contained within $\bar{b}_j$. This means each edge of $\beta$ aligns with the extended portion of some boundary segment. 2. **Disjoint interiors:** The portions of the boundary segments $b_j$ between their outer endpoints and the points $u_j$ must have pairwise disjoint relative interiors. This condition ensures that the conformal path follows the boundary segments in a non-overlapping manner. ::: Conformal paths are essentially polygonal paths that are \"glued\" together from pieces of extended boundary segments, respecting their directions and disjointness. ### ChainBSP Algorithm (Algorithm [6](#alg:chainbsp){reference-type="ref" reference="alg:chainbsp"}): Partitioning along Conformal Paths {#subsubsection:chainbsp_algorithm} The algorithm `ChainBSP(`$\beta$`)` provides a method for partitioning space based on a conformal path $\beta$. It partitions the plane sequentially along the supporting lines of the edges of $\beta$, but in reverse order of their appearance in the path. ::: {.alg:chainbsp .algorithm} **Algorithm 6** (title=Algorithm 1: ChainBSP($\beta$), colback=blue!20, colframe=blue!75!black). **Algorithm 1.** `ChainBSP(`$\beta$`)` **Input:** A conformal path $\beta = (u_0, u_1, \ldots, u_t)$ such that for each $j = 1, 2, \ldots, t$, there is a boundary segment $b_j \in B$ with $\overline{u_{j-1}u_j} \subseteq \bar{b}_j$. **For** $j = 0, 1, \ldots, t-1$ **do**: - Partition every cell that intersects the line segment between the outer endpoint of $b_{t-j}$ and point $u_{t-j}$ by the supporting line of $b_{t-j}$. **Complexity Analysis:** For a conformal path with $t$ edges, `ChainBSP(`$\beta$`)` performs $t$ partitioning steps. In each step, partitioning a cell along a line takes time proportional to the number of segments intersecting the cell. A detailed complexity analysis would depend on how segments are managed and updated across partitions, but for now, we focus on the structural properties of the partition. ::: ### Proposition [7](#prop:chainbsp_boundary_cuts){reference-type="ref" reference="prop:chainbsp_boundary_cuts"}: Bounded Boundary Segment Cuts in ChainBSP {#subsubsection:chainbsp_boundary_cuts} A key property of `ChainBSP(`$\beta$`)` is that it limits the fragmentation of boundary segments. ::: {.prop:chainbsp_boundary_cuts .proposition} **Proposition 7** (title=Proposition 2.3: Bounded Boundary Segment Cuts in ChainBSP, colback=red!20, colframe=red!75!black). *For a conformal path $\beta = (u_0, u_1, \ldots, u_t)$, the `ChainBSP(`$\beta$`)` algorithm cuts every boundary segment at most once. More specifically, only the very first partitioning step in the algorithm, which uses the supporting line of the segment $\overline{u_{t-1}u_t}$ (derived from $b_t$), has the potential to cut boundary segments. Subsequent partitioning steps will not introduce further cuts to boundary segments.* ::: This proposition highlights the efficiency of `ChainBSP(`$\beta$`)` in controlling the fragmentation of boundary segments. ### Interior Segment Cuts in ChainBSP and Need for Simplification {#subsubsection:chainbsp_interior_cuts} While `ChainBSP(`$\beta$`)` effectively limits cuts on boundary segments, it may, in its basic form, cut interior segments multiple times. For a conformal path $\beta$ with $t$ edges, an interior segment could potentially be cut up to $t$ times, as each partitioning line in `ChainBSP(`$\beta$`)` could intersect it. To address this, we will introduce a \"simplification\" process for conformal paths. We will transform a conformal path $\beta$ into another conformal path $\delta$ such that `ChainBSP(`$\delta$`)` ensures that every input segment, including interior segments, is cut at most a constant number of times, i.e., $O(1)$ times. This simplification is crucial for achieving the desired BSP size bounds. # Proof of Lemma [4](#lemma:subbsp_core_lemma){reference-type="ref" reference="lemma:subbsp_core_lemma"}: SubBSP Construction {#sec:proof_lemma3} Let $B$ be a set of $m$ boundary segments in a convex cell $C$, and let $k$ be an integer, $1 \leq k \leq m$. We now detail the construction of `SubBSP(B, C, k)`. The process involves several steps: ## Polygonal Paths $\alpha_i$ Construction {#subsec:polygonal_paths_construction} We begin by constructing polygonal paths $\alpha_i$. Label the boundary segments as $B = \{s_1, s_2, \ldots, s_m\}$. For each boundary segment $s_i$, we extend it along its direction until it hits another segment, the boundary of $C$, or a previously created extension. ### Algorithm ConvexPartition(B) (Algorithm [8](#alg:convexpartition){reference-type="ref" reference="alg:convexpartition"}): Extended Segments `ext(`$s_i$`)` and $\hat{s}_i$ {#subsubsection:convexpartition_algorithm} ::: {.alg:convexpartition .algorithm} **Algorithm 8** (title=Algorithm 2: ConvexPartition(B), colback=blue!20, colframe=blue!75!black). **Algorithm 2.** `ConvexPartition(B)` **For** $i = 1$ to $m$, **do**: - Let `ext(`$s_i$`)` be the line segment along $\vec{s}_i$ between the inner endpoint of $s_i$ and the first point along $\vec{s}_i$ that lies in $(\bigcup_{j=1}^{i-1} s_j) \cup (\bigcup_{j=1}^{i-1} \text{ext}(s_j)) \cup \partial C$. **Complexity Analysis:** The complexity of `ConvexPartition(B)` is dominated by finding the first intersection point for each segment extension. Using efficient geometric data structures for segment intersection queries, this can be done in $O(m \log m)$ time for all $m$ segments. ::: Let $\hat{s}_i = s_i \cup \text{ext}(s_i)$ be the extended segment. The relative interiors of the extended segments $\hat{s}_i$ are pairwise disjoint. For each $s_i \in B$, we construct a path $\alpha_i$ that follows the directions of the extended segments. ### Algorithm PathBuilder(i, R) (Algorithm [9](#alg:pathbuilder){reference-type="ref" reference="alg:pathbuilder"}): Constructing Paths $\alpha_i$ {#subsubsection:pathbuilder_algorithm} ::: {.alg:pathbuilder .algorithm} **Algorithm 9** (title=Algorithm 3: PathBuilder(i, R), colback=blue!20, colframe=blue!75!black). **Algorithm 3.** `PathBuilder(i, R)` Let the first vertex of $\alpha_i$ be the outer endpoint of $s_i$, and let $s := \hat{s}_i$. **Until** the head of $s$ lies along $\partial C$ or in the relative interior of a previous edge of $\alpha_i$. - Append the head of segment $s$ to $\alpha_i$. - Let $b \in B$ be the boundary segment such that the head of $s$ lies in the relative interior of $\hat{b}$, and set $s := \hat{b}$. **Complexity Analysis:** The `PathBuilder` algorithm constructs each path $\alpha_i$ by traversing extended segments. In the worst case, a path might visit a significant portion of the arrangement of extended segments. However, since the number of boundary segments is $m$, and each extension is computed efficiently, the complexity of building all paths $\alpha_i$ for all $i$ from 1 to $m$ is bounded by $O(m^2)$ in a naive implementation, but can be optimized to $O(m \log m)$ with efficient spatial data structures. ::: **Figure [2](#fig:polygonal_paths){reference-type="ref" reference="fig:polygonal_paths"}** illustrates the construction of these paths. <figure id="fig:polygonal_paths"> <table> <tbody> <tr> <td style="text-align: center;"><img src="example-image-a" style="width:30.0%" alt="image" /></td> <td style="text-align: center;"><img src="example-image-b" style="width:30.0%" alt="image" /></td> <td style="text-align: center;"><img src="example-image-a" style="width:30.0%" alt="image" /></td> </tr> <tr> <td style="text-align: center;">(a) Boundary segments</td> <td style="text-align: center;">(b) Extended boundary segments</td> <td style="text-align: center;">(c) Paths <span class="math inline">$\alpha_i$</span></td> </tr> </tbody> </table> <figcaption>Polygonal paths construction.</figcaption> </figure> ### Paths $\alpha_i$, Conformal Paths, and Convex Cycles $\varphi_i$ {#subsubsection:paths_conformal_cycles} ::: {.prop:paths_conformal_cycles .proposition} **Proposition 10** (title=Proposition 3.1: Paths $\alpha_i$ Decomposition, colback=red!20, colframe=red!75!black). *If a path $\alpha_i$, $1 \leq i \leq m$, terminates at a point $q$ in the interior of $C$, then $\alpha_i$ is composed of a conformal path $\alpha'_i$ from the outer endpoint of $s_i$ to $q$, and a directed convex cycle $\varphi_i$.* ::: Let $R_i = \bigcup \{s_j : \alpha_i \cap \hat{s}_j \neq \emptyset\}$ be the union of extended boundary segments visited by path $\alpha_i$. The cycle $\varphi_i$ is the boundary of one of the convex faces formed by $R_i$. ### Proposition on Intersection of Paths $\alpha_i$ and $\alpha_j$ and Common Cycles {#subsubsection:path_intersection_common_cycles} ::: {.prop:path_intersection_common_cycles .proposition} **Proposition 11** (title=Proposition 3.2: Intersection of Paths and Common Cycles, colback=red!20, colframe=red!75!black). *For every $1 \leq i < j \leq m$, if paths $\alpha_i$ and $\alpha_j$ intersect, then $\varphi_i = \varphi_j$.* ::: ### Proposition on Ray Crossing Subpaths $\psi$ of $\alpha_i$ {#subsubsection:ray_crossing_subpaths} ::: {.prop:ray_crossing_subpaths .proposition} **Proposition 12** (title=Proposition 3.3: Ray Crossing Subpaths, colback=red!20, colframe=red!75!black). *Let $\psi = (u_0, u_1, \ldots, u_t)$ be a subpath of $\alpha'_i$ for some $1 \leq i \leq m$. Then the ray $\overrightarrow{u_{t-1}u_t}$ cannot cross path $\psi$.* ::: ## Selecting Paths and Constructing Dual Graph $G_P$ {#subsec:path_selection_dual_graph} Let $R = \bigcup_{i=1}^m \alpha_i$ be the union of all paths. For any subset $P \subseteq \{1, 2, \ldots, m\}$, let $R_P = \bigcup_{i \in P} \alpha_i$. $R_P$ decomposes $C$ into faces $F_P$. We define a dual graph $G_P$ where nodes are faces in $F_P$, and adjacency is defined by sharing a boundary segment's outer endpoint. ### Set of Paths $R_P = \bigcup_{i \in P} \alpha_i$ and Faces $F_P$ {#subsubsection:paths_faces_rp_fp} The set $R_P$ is formed by taking the union of the polygonal paths $\alpha_i$ for all indices $i$ in the chosen subset $P$. This set of paths $R_P$ acts as a planar subdivision within the convex cell $C$. The faces $F_P$ are then the connected components of the region obtained by removing $R_P$ from $C$, i.e., $F_P = C \setminus R_P$. These faces are convex polygons or unbounded convex regions. ### Dual Graph $G_P$ Definition: Faces as Nodes {#subsubsection:dual_graph_gp_definition} ::: {.def:dual_graph_gp .definition} **Definition 13** (title=Definition 3.4: Dual Graph $G_P$, colback=green!20, colframe=green!75!black). The dual graph $G_P$ is a graph where each node represents a face in $F_P$. Two nodes in $G_P$ are adjacent if and only if their corresponding faces in $F_P$ are adjacent along the boundary, specifically if they are both incident to a common outer endpoint of some boundary segment $s_i$, where $i \in P$. ::: ### Algorithm PathSelector(B, C, k) (Algorithm [14](#alg:pathselector){reference-type="ref" reference="alg:pathselector"}): Selecting Paths to Control Face Complexity {#subsubsection:pathselector_algorithm} ::: {.alg:pathselector .algorithm} **Algorithm 14** (title=Algorithm 4: PathSelector(B, C, k), colback=blue!20, colframe=blue!75!black). **Algorithm 4.** `PathSelector(B, C, k)` Let $P := \{1, 2, \ldots, m\}$. **For** $i =1$ to $m$, **do**: - If the faces of $F_P$ incident to the outer endpoint of $s_i$ jointly intersect at most $m/(2k) - 2$ boundary segments, then let $P := P \setminus \{i\}$. **Output** $P$. **Complexity Analysis:** The `PathSelector` algorithm iterates through each boundary segment $s_i$. In each iteration, it needs to check the number of boundary segments intersected by the faces incident to the outer endpoint of $s_i$. This requires traversing the faces of the arrangement $F_P$ and counting segment intersections, which can be done in time related to the complexity of the arrangement. A detailed analysis would depend on the data structure used to represent $F_P$, but a reasonable implementation can achieve a runtime of $O(m^2)$ for the entire `PathSelector` algorithm, and with optimization, potentially closer to $O(m \log m)$. ::: ### Proposition [15](#prop:boundary_segment_intersections_path_selection){reference-type="ref" reference="prop:boundary_segment_intersections_path_selection"}: Boundary Segment Intersections per Face after Path Selection {#subsubsection:boundary_segment_intersections_path_selection} ::: {.prop:boundary_segment_intersections_path_selection .proposition} **Proposition 15** (title=Proposition 3.5: Boundary Segment Intersections after Path Selection, colback=red!20, colframe=red!75!black). *Let $P = \texttt{PathSelector(B, C, k)}$.* - *Every face $f \in F_P$ intersects at most $m/(2k) - 1$ boundary segments.* - *If $f_1, f_2 \in F_P$, $f_1 \neq f_2$, are adjacent along the boundary, then they jointly intersect at least $m/(2k) - 1$ boundary segments.* ::: ## Dual Graph of Connected Components $H_P$ {#subsec:dual_graph_connected_components} ### Nodes: Connected Components of $R_P$ {#subsubsection:nodes_connected_components_rp} In addition to the dual graph $G_P$ on faces, we define another dual graph $H_P$ that captures the connectivity of the components of $R_P$. The nodes of $H_P$ correspond to the connected components of the path diagram $R_P = \bigcup_{i \in P} \alpha_i$. ### Edges: Adjacency through Faces in $F_P$ {#subsubsection:edges_adjacency_faces_fp} Two nodes in $H_P$ are connected by an edge if and only if their corresponding connected components in $R_P$ are adjacent to the same face in the face subdivision $F_P$. Adjacency here means that the components and the face share a boundary. ### Tree Structure of $H_P$ {#subsubsection:tree_structure_hp} A crucial property of the dual graph $H_P$ is that it is always a tree. This tree structure reflects the hierarchical and non-cyclic nature of how the connected components of $R_P$ decompose the convex cell $C$. The tree structure of $H_P$ is essential for the recursive partitioning strategy used in the `SubBSP` algorithm. **Figure [3](#fig:dual_graph){reference-type="ref" reference="fig:dual_graph"}** illustrates the dual graph of connected components. <figure id="fig:dual_graph"> <table> <tbody> <tr> <td style="text-align: center;"><img src="example-image-a" style="width:30.0%" alt="image" /></td> <td style="text-align: center;"><img src="example-image-b" style="width:30.0%" alt="image" /></td> <td style="text-align: center;"><img src="example-image-a" style="width:30.0%" alt="image" /></td> </tr> <tr> <td style="text-align: center;">(a) Components of R</td> <td style="text-align: center;">(b) Convex hull of components</td> <td style="text-align: center;">(c) Dual graph <span class="math inline">$H_P$</span></td> </tr> </tbody> </table> <figcaption>Dual graph of connected components.</figcaption> </figure> ## Lemma [16](#lemma:lemma_3_1){reference-type="ref" reference="lemma:lemma_3_1"}: Bounding Paths within Connected Components of $H_P$ {#subsec:lemma_3_1} ::: {.lemma:lemma_3_1 .lemma} **Lemma 16** (title=Lemma 3.6: Bounding Paths in Connected Components, colback=red!20, colframe=red!75!black). *Let $P = \texttt{PathSelector(B,C,k)}$, and let $Q_1, Q_2, \ldots, Q_l$ be connected components of $R_P$ corresponding to a simple path in $H_P$. Then $Q_1, Q_2, \ldots, Q_l$ jointly contain at most $10k$ paths $\alpha_i$, $i \in P$.* ::: *Proof of Lemma [16](#lemma:lemma_3_1){reference-type="ref" reference="lemma:lemma_3_1"}:* \[Proof content will be added here based on the transcript and geometric reasoning. This is a placeholder for the detailed proof.\] ## Reduction to Single Component: Sectors $C'$ and Components $R'_P$ {#subsec:reduction_single_component} The diagram $R_P = \bigcup_{i \in P} \alpha_i$ may consist of several connected components. To simplify the partitioning process, we aim to separate these components and reduce the problem to handling a single connected component at a time. Recall that each connected component of $R_P$ lies within a unique sector of the cell $C$. These sectors are formed by partitioning $C$ using chords. ## Lemma [17](#lemma:lemma_3_2){reference-type="ref" reference="lemma:lemma_3_2"} and Algorithm SubBSP {#subsec:lemma_3_2_subbsp_algorithm} ::: {.lemma:lemma_3_2 .lemma} **Lemma 17** (title=Lemma 3.7: Properties of CompBSP, colback=red!20, colframe=red!75!black). *Let $R'_P$ be a connected component of $R_P$ containing $h \in \mathbb{N}$ paths $\alpha_i$. Let $C' \subseteq C$ be the sector of $C$ containing $R'_P$. There exists a BSP algorithm `CompBSP(B,C’, R’p)` such that:* 1. *Every boundary segment in $C'$ is cut $O(1)$ times.* 2. *Every interior segment is cut at most $O(h)$ times.* 3. *Every cell produced by `CompBSP(B,C’, R’p)` intersects less than $m/k$ boundary segments.* ::: ### Algorithm SubBSP(B, C, k) (Algorithm [18](#alg:subbsp){reference-type="ref" reference="alg:subbsp"}): Recursive Partitioning Strategy {#subsubsection:subbsp_algorithm} ::: {.alg:subbsp .algorithm} **Algorithm 18** (title=Algorithm 5: SubBSP(B, C, k), colback=blue!20, colframe=blue!75!black). **Algorithm 5.** `SubBSP(B, C, k)` 1. **Sector Partitioning:** For every non-leaf component $R'_P \subseteq R_P$ in the dual graph $H_P$, partition the cell $C$ along the chord $e(R'_P)$ associated with that component. This step divides $C$ into sectors, each containing a single connected component of $R_P$. 2. **Component Processing:** For each connected component $R'_P \subseteq R_P$ and its corresponding sector $C'$, recursively call `CompBSP(B, C’, R’p)` to further partition within each sector. **Complexity Analysis:** The complexity of `SubBSP(B, C, k)` is dominated by the calls to `CompBSP` and the initial partitioning along chords. If there are $l$ connected components, and the complexity of `CompBSP` is $T_{CompBSP}$, the complexity of `SubBSP` is roughly $O(m \log m + l \cdot T_{CompBSP})$, where $O(m \log m)$ accounts for path selection and dual graph construction. ::: ## Processing a Single Component $R'_P$ {#subsec:processing_single_component} Now we focus on processing a single connected component $R'_P$ of $R_P$ within its sector $C'$. Let $R'$ be the component of $R$ that contains $R'_P$. We decompose $R'_P$ into a set of non-overlapping conformal paths $\Gamma = \{\beta_1, \beta_2, \ldots, \beta_g\}$. This decomposition allows us to apply `ChainBSP` in a structured way. ## Path Simplification: Algorithm Simplify {#subsec:path_simplification_algorithm_simplify} ### Algorithm Simplify(B,C,$\gamma$) (Algorithm [19](#alg:simplify){reference-type="ref" reference="alg:simplify"}): Simplifying Convex Conformal Paths {#subsubsection:simplify_algorithm} ::: {.alg:simplify .algorithm} **Algorithm 19** (title=Algorithm 6: Simplify(B,C,$\gamma$), colback=blue!20, colframe=blue!75!black). **Algorithm 6.** `Simplify(B,C,`$\gamma$`)` **Input:** A set $B$ of boundary segments in a convex cell $C$, and a convex conformal path $\gamma = (u_e, u_{e+1}, \ldots, u_t)$ which makes right turns only. Set $\delta := \gamma$. **While** $\delta$ has four consecutive vertices $(a_0, a_1, a_2, a_3)$ such that there are boundary segments $b_1, b_3 \in B$ with $\overline{a_0a_1} \subseteq b_1$ and $\overline{a_2a_3} \subseteq b_3$; and the intersection point $x$ of the supporting line of $b_1$ and $b_3$ lies in the part of $b_3$ between the outer endpoint of $b_3$ and $a_2$, **do**: - Replace the subpath $(a_0, a_1, a_2, a_3)$ by $(a_0, x, a_3)$ in $\delta$. **Output:** $\delta$. **Complexity Analysis:** The `Simplify` algorithm iteratively reduces the number of vertices in the conformal path $\gamma$. In each iteration, it computes the intersection of two lines and checks a geometric condition. The number of vertices is reduced in each step, and the overall number of vertices in $\gamma$ is at most $m$. Thus, the complexity of `Simplify` is bounded by $O(m^2)$ in a naive implementation, but can be optimized to be more efficient with careful implementation of intersection checks and path updates. ::: ### Proposition [20](#prop:interior_segment_cuts_simplification){reference-type="ref" reference="prop:interior_segment_cuts_simplification"}: Interior Segment Cuts after Simplification: $O(1)$ Cuts {#subsubsection:interior_segment_cuts_simplification} ::: {.prop:interior_segment_cuts_simplification .proposition} **Proposition 20** (title=Proposition 3.8: Interior Segment Cuts after Simplification, colback=red!20, colframe=red!75!black). *If $\gamma$ is a convex conformal path and $\delta = \texttt{Simplify(B,C,$\gamma$)}$, then `ChainBSP(`$\delta$`)` cuts every interior segment $O(1)$ times.* ::: ## Proof of Lemma [17](#lemma:lemma_3_2){reference-type="ref" reference="lemma:lemma_3_2"} and Algorithm CompBSP {#subsec:proof_lemma_12_compbsp_algorithm} ### Algorithm CompBSP(B,C', R'p) (Algorithm [21](#alg:compbsp){reference-type="ref" reference="alg:compbsp"}): Processing a Component using Simplified Paths {#subsubsection:compbsp_algorithm} ::: {.alg:compbsp .algorithm} **Algorithm 21** (title=Algorithm 7: CompBSP(B,C', R'p), colback=blue!20, colframe=blue!75!black). **Algorithm 7.** `CompBSP(B,C’, R’p)` **Input:** Boundary segments $B$ in cell $C'$, and a connected component $R'_P \subseteq R_P$. Decompose $R'_P$ into non-overlapping conformal paths $\Gamma = \{\beta_1, \beta_2, \ldots, \beta_g\}$. Let $\delta_i = \texttt{Simplify}(B,C',\gamma_i)$ for each $\gamma_i \in \Gamma$. **For** $i = 1, 2, \ldots, g$, **do**: - Apply `ChainBSP(`$\delta_i$`)`. **Complexity Analysis:** The `CompBSP` algorithm iterates through the simplified conformal paths $\delta_i$. For each path, it calls `ChainBSP`. If there are $g$ paths and the maximum length of a simplified path is $z$, and assuming `ChainBSP` on a path of length $z$ takes $O(z \cdot m')$ time where $m'$ is the number of segments in the current cell, the total complexity of `CompBSP` would be roughly $O(\sum_{i=1}^g |\delta_i| \cdot |B|)$. Since the total number of edges in all $\delta_i$ is related to the number of paths $h$ in $R'_P$, and simplification reduces path complexity, a reasonable bound for `CompBSP` is achievable within $O(h \cdot |B|)$ or $O(h \cdot m \log m)$ with efficient implementations. ::: ### Proposition [22](#prop:face_intersections_bounding_segments){reference-type="ref" reference="prop:face_intersections_bounding_segments"}: Face Intersections: Bounding Remaining Boundary Segments {#subsubsection:face_intersections_bounding_segments} ::: {.prop:face_intersections_bounding_segments .proposition} **Proposition 22** (title=Proposition 3.9: Face Intersections in CompBSP, colback=red!20, colframe=red!75!black). *Every (open) face $f \in F'_P$ produced by `CompBSP(B,C’, R’p)` intersects at most $m/(2k) - 1$ boundary segments.* ::: # Proof of Theorem [\[theorem:optimal_bsp_size\]](#theorem:optimal_bsp_size){reference-type="ref" reference="theorem:optimal_bsp_size"}: Optimal BSP Size {#sec:proof_theorem1} ## Recursive BSP Algorithm (Algorithm [23](#alg:bsp){reference-type="ref" reference="alg:bsp"}) {#subsec:recursive_bsp_algorithm} ### Algorithm BSP(S, C, k) (Algorithm [23](#alg:bsp){reference-type="ref" reference="alg:bsp"}): Top-Level BSP Construction {#subsubsection:bsp_algorithm} ::: {.alg:bsp .algorithm} **Algorithm 23** (title=Algorithm 8: BSP(S, C, k), colback=blue!20, colframe=blue!75!black). **Algorithm 8.** `BSP(S, C, k)` 1. **Boundary Segment Check:** If the set of boundary segments $B$ in the current cell $C$ is not empty (i.e., $|B| > 0$), proceed with subdivision. Otherwise, if $|B| = 0$, and there are still segments in $S$ within $C$, partition along an arbitrary segment. 2. **Subproblem Call:** If $|B| > 0$, call `SubBSP(B, C, min(|B|,k))`. The parameter $k$ is capped at $|B|$ to avoid exceeding the number of boundary segments. If $|B| = 0$ and $S$ is not empty, partition $C$ along the supporting line of an arbitrary segment $s \in S$. 3. **Recursive Calls:** For each cell $C'$ produced in step 1 that still contains segments (i.e., $S(C') \neq \emptyset$), recursively call `BSP(C’, S(C’), k)` to continue the partitioning process in the subcells. **Complexity Analysis:** The overall runtime of `BSP(S, C, k)` depends on the depth of recursion and the complexity of `SubBSP`. With $k = \lceil \frac{\log n}{\log \log n} \rceil$, and given the properties of `SubBSP`, the algorithm achieves a total runtime of $O(n \log^3 n / \log \log n)$, as discussed in Section [5.5](#sec:bsp_construction_runtime){reference-type="ref" reference="sec:bsp_construction_runtime"}. ::: ## Lemma [24](#lemma:lemma_4_1){reference-type="ref" reference="lemma:lemma_4_1"}: BSP Size of $O(n \log n / \log \log n)$ {#subsec:lemma_4_1} ::: {.lemma:lemma_4_1 .lemma} **Lemma 24** (title=Lemma 4.1: Optimal BSP Size, colback=red!20, colframe=red!75!black). *For a set $S_0$ of $n$ disjoint line segments in a convex cell $C_0$, `BSP`$(S_0, C_0, \lceil \frac{\log n}{\log \log n} \rceil)$ is a BSP for $S$, and it partitions $S$ into $O(n \log n / \log \log n)$ fragments.* ::: *Proof of Lemma [24](#lemma:lemma_4_1){reference-type="ref" reference="lemma:lemma_4_1"}:* \[Proof content will be added here based on the charging scheme and recursive analysis described in the transcript. This is a placeholder for the detailed proof.\] # Auto-partitions for Disjoint Line Segments {#sec:auto_partitions} ## Adapting ChainBSP for Auto-partitions {#subsec:adapting_chainbsp_autopartitions} We adjust the BSP algorithm to obtain an auto-partition of size $O(n \log n / \log \log n)$. We use `ChainBSP(`$\delta$`)` as a building block, ensuring the paths $\delta$ satisfy conditions for auto-partitioning. ## Proposition [25](#prop:chainbsp_autopartition_conditions){reference-type="ref" reference="prop:chainbsp_autopartition_conditions"}: Conditions for ChainBSP to be an Auto-partition {#subsec:chainbsp_autopartition_conditions} ::: {.prop:chainbsp_autopartition_conditions .proposition} **Proposition 25** (title=Proposition 5.1: ChainBSP as Auto-partition, colback=red!20, colframe=red!75!black). *Let $\delta = (v_0, v_1, \ldots, v_z)$ be a convex conformal path. Assume that $\delta$ and the boundary segments $b_j$ with $\overline{v_{j-1}v_j} \subseteq b_j$, for $j = 1, 2, \ldots, z$, lie in a single cell. `ChainBSP(`$\delta$`)` is an auto-partition if the supporting line of $b_z$ does not cross the part of $b_1$ between the outer endpoint of $b_1$ and point $v_1$.* ::: ## Proposition [26](#prop:simplified_chainbsp_autopartition_conditions){reference-type="ref" reference="prop:simplified_chainbsp_autopartition_conditions"}: Conditions for Simplified ChainBSP to be an Auto-partition {#subsec:simplified_chainbsp_autopartition_conditions} ::: {.prop:simplified_chainbsp_autopartition_conditions .proposition} **Proposition 26** (title=Proposition 5.2: Simplified ChainBSP as Auto-partition, colback=red!20, colframe=red!75!black). *Let $\gamma_i \in \Gamma$, and $\delta_i = \texttt{Simplify(B,C,$\gamma_i$)}$. Assume that $\delta_i = (v_0, v_1, \ldots, v_z)$ and the boundary segments $b_j$ with $\overline{v_{j-1}v_j} \subseteq b_j$, for $j = 1, 2, \ldots, z$, lie in a single cell. `ChainBSP(`$\delta_i$`)` is an auto-partition if* - *$\gamma_i$ is not part of the convex cycle $\varphi$, or* - *$\gamma_i$ is part of the convex cycle $\varphi$ but the turning angle of $\gamma_i$ at most $180^\circ$.* ::: ## Lemma [27](#lemma:subauto_lemma){reference-type="ref" reference="lemma:subauto_lemma"}: SubAuto Algorithm and Properties {#subsec:subauto_lemma} ::: {.lemma:subauto_lemma .lemma} **Lemma 27** (title=Lemma 5.3: Properties of SubAuto, colback=red!20, colframe=red!75!black). *Let $S$ be a finite set of disjoint line segments in the plane. For every integer $k$, $1 \leq k \leq |B|$, there is an auto-partition `SubAuto(B,C,k)` such that* - *Every boundary segment in $B$ is cut at most $O(1)$ times on average;* - *Every interior segment in $I$ is cut at most $O(k)$ times;* - *Every cell produced by `SubAuto(B,C,k)` intersects at most $|B|/k$ segments in $B$.* ::: ## Construction of a BSP in O(n polylog n) Time {#sec:bsp_construction_runtime} \[Content about the construction time will be added here.\] ## Conclusion {#sec:conclusion} \[Conclusion content will be added here.\] ## Exercises {#sec:exercises} \[Exercises content will be added here.\] ## References {#sec:references} ::: thebibliography 99 P. K. Agarwal, E. F. Grove, T. M. Murali, and J. S. Vitter, Binary space partitions for fat rectangles, SIAM J. Comput. 29 (2000), 1422-1448. S. Ar, B. Chazelle, and A. Tal, Self-customized BSP trees for collision detection, Comput. Geom. Theory Appl. 15 (1-3) (2000), 91--102. S. Ar, G. Montag, and A. Tal, Deferred, self-organizing BSP trees, Comput. Graph. Forum 21 (3) (2002), 269--278. S. Arya, Binary space partitions for axis-parallel line segments: size-height tradeoffs, Inform. Proc. Letts. 84 (4) (2002), 201-206. S. Arya, T. Malamatos, and D.M. Mount, Nearly optimal expected-case planar point location, in Proc. 41st Sympos. Foundations of Comp. Sci., IEEE Press, 2000, pp. 208--218. T. Asano, M. de Berg, O. Cheong, L.J. Guibas, J. Snoeyink, and H. Tamaki, Spanning trees crossing few barriers, Discrete Comput. Geom. 30 (2003), 591--606. M. de Berg, Linear size binary space partitions for fat objects, in Proc. 3rd European Sympos. Algorithms, vol. 979 of LNCS, Springer, Berlin, 1995, pp. 252-263. M. de Berg, Linear size binary space partitions for uncluttered scenes, Algorithmica 28 (3) (2000), 353-366. M. de Berg, H. David, M. Katz, M. Overmars, A.F. van der Stappen, and J. Vleugels, Guarding scenes against invasive hypercubes, Comput. Geom. Theory Appl. 26 (2003), 99--117. M. de Berg, M. de Groot, and M. Overmars, New results on binary space partitions in the plane, Comput. Geom. Theory Appl. 8 (1997), 317-333. M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, Computational Geometry: Algorithms and Applications, 3rd edition, Springer, Berlin, 2008. M. de Berg and M. Streppel, Approximate range searching using binary space partitions, Comput. Geom. Theory Appl. 33 (3) (2006), 139--151. B. Chazelle, H. Edelsbrunner, M. Grigni, L. J. Guibas, J. Hershberger, M. Sharir, and J. Snoeyink, Ray shooting in polygons using geodesic triangulations, Algorithmica 12 (1994), 54-68. N. Chin and S. Feiner, Fast object-precision shadow generation for areal light sources using BSP trees, Comput. Graph. 25 (1992), 21-30. A. Dumitrescu, J. S. B. Mitchell, and M. Sharir, Binary space partitions for axis-parallel segments, rectangles, and hyperrectangles, Discrete Comput. Geom. 31 (2) (2004), 207--227. H. Fuchs, Z. M. Kedem, and B. Naylor, On visible surface generation by a priori tree structures, Comput. Graph. 14 (3) (1980), 124--133. Proc. SIGGRAPH. J. Hershberger and S. Suri, A pedestrian approach to ray shooting: Shoot a ray, take a walk, J. Algorithms 18 (3) (1995), 403-431. J. Hershberger, S. Suri and Cs. D. Tóth, Binary space partitions of orthogonal subdivisions, SIAM J. Comput. 34 (6) (2005), 1380--1397. M. Ishaque, B. Speckmann, and Cs. D. Tóth, Shooting permanent rays among disjoint polygons in the plane, in Proc. 25th ACM Sympos. Comput. Geom. ACM Press, 2009, these proceedings. C.S. Mata and J.S.B. Mitchell, Approximation algorithms for geometric tour and network design problems, in Proc. 11th ACM Sympos. Comput. Geom. ACM Press, 1995, pp. 360--369. B. Naylor, Constructing good partitioning trees, Proc. Graphics Interface, 1993, Canadian Human-Computer Communications Society, Toronto, pp. 181--191. M. S. Paterson and F. F. Yao, Efficient binary space partitions for hidden-surface removal and solid modeling, Discrete Comput. Geom. 5 (1990), 485--503. M. S. Paterson and F. F. Yao, Optimal binary space partitions for orthogonal objects, J. Algorithms 13 (1992), 99--113. R. A. Schumacker, R. Brand, M. Gilliland, and W. Sharp, Study for applying computer generated images to visual simulation, Tech. Rep. AFHRL--TR--69--14, San Antonio, TX, 1969. W. C. Thibault and B. F. Naylor, Set operations on polyhedra using binary space partitioning trees, Comput. Graph. 21 (4) (1987), 153--162, Proc. SIGGRAPH '87. Cs. D. Tóth, A note on binary plane partitions, Discrete Comput. Geom. 30 (2003), 3--16. Cs. D. Tóth, Binary space partition for axis-aligned fat rectangles, SIAM J. Comput. 38 (1) (2008), 429--447. Cs. D. Tóth, Binary space partition for line segments with a limited number of directions, SIAM J. Comput. 32 (2) (2003), 307--325. :::

Introduction

Binary Space Partition (BSP) Definition

Applications of BSPs

Computer Graphics: Hidden Surface Removal and Z-buffering

Solid Modeling

Shadow Generation

Motion Planning

Range Searching

Network Design

BSP Complexity and Fragmentation

Research on Minimizing BSP Size

Paterson and Yao’s \(O(n \log n)\) Result for Disjoint Line Segments

Randomized BSP Construction and Expected Size

Special Cases and Object Types

Goal: Asymptotically Optimal \(O(n \log n / \log \log n)\) BSP

Preliminaries

BSP Size Measurement: Fragments and Cuts

Working within Convex Cells

Initial Cell \(C_0\)

Segment Types Relative to Cell Boundary \(\partial C\)

Free Segments

Boundary Segments

Interior Segments

Prioritizing Free Cuts for Simplification

SubBSP Algorithm and Lemma 4: Core Partitioning Lemma

BSPs Along Conformal Paths

Directed Boundary Segments and Rays \(\vec{b}\), \(\bar{b}\)

Definition of Conformal Path \(\beta\)

ChainBSP Algorithm (Algorithm 6): Partitioning along Conformal Paths

Proposition 7: Bounded Boundary Segment Cuts in ChainBSP

Interior Segment Cuts in ChainBSP and Need for Simplification

Proof of Lemma 4: SubBSP Construction

Polygonal Paths \(\alpha_i\) Construction

Algorithm ConvexPartition(B) (Algorithm 8): Extended Segments ext(\(s_i\)) and \(\hat{s}_i\)

Algorithm PathBuilder(i, R) (Algorithm 9): Constructing Paths \(\alpha_i\)

Paths \(\alpha_i\), Conformal Paths, and Convex Cycles \(\varphi_i\)

Proposition on Intersection of Paths \(\alpha_i\) and \(\alpha_j\) and Common Cycles

Proposition on Ray Crossing Subpaths \(\psi\) of \(\alpha_i\)

Selecting Paths and Constructing Dual Graph \(G_P\)

Set of Paths \(R_P = \bigcup_{i \in P} \alpha_i\) and Faces \(F_P\)

Dual Graph \(G_P\) Definition: Faces as Nodes

Algorithm PathSelector(B, C, k) (Algorithm 14): Selecting Paths to Control Face Complexity

Proposition 15: Boundary Segment Intersections per Face after Path Selection

Dual Graph of Connected Components \(H_P\)

Nodes: Connected Components of \(R_P\)

Edges: Adjacency through Faces in \(F_P\)

Tree Structure of \(H_P\)

Lemma 16: Bounding Paths within Connected Components of \(H_P\)

Reduction to Single Component: Sectors \(C'\) and Components \(R'_P\)