Humans excel at efficiently navigating through crowds without collision by focusing on specific visual regions relevant to navigation. However, most robotic visual navigation methods rely on deep learning models pre-trained on vision tasks, which prioritize salient objects—not necessarily relevant to navigation and potentially misleading. Alternative approaches train specialized navigation models from scratch, requiring significant computation. On the other hand, self-supervised learning has revolutionized computer vision and natural language processing, but its application to robotic navigation remains underexplored due to the difficulty of defining effective self-supervision signals. Motivated by these observations, in this work, we propose a Self-Supervised Vision-Action Model for Visual Navigation Pre-Training (VANP). Instead of detecting salient objects that are beneficial for tasks such as classification or detection, VANP learns to focus only on specific visual regions that are relevant to the navigation task. To achieve this, VANP uses a history of visual observations, future actions, and a goal image for self-supervision, and embeds them using two small Transformer Encoders. Then, VANP maximizes the information between the embeddings by using a mutual information maximization objective function. We demonstrate that most VANP-extracted features match with human navigation intuition. VANP achieves comparable performance as models learned end-to-end with half the training time and models trained on a large-scale, fully supervised dataset, i.e., ImageNet, with only 0.08% data.

§ INTRODUCTION

In recent years, imitation learning, particularly behavior cloning <cit.>, has become a leading approach for visual navigation models <cit.>. However, the performance of these models heavily relies on the visual features extracted by the model's visual encoder. Although the limited memory and processing power onboard robots restrict the size of models deployable in real time, with such limitations we still need accurate and efficient onboard visual encoders, making convolutional neural networks (CNNs) more desirable than larger Vision Transformer models (ViTs) <cit.>.

Comparison of Activation Maps Learned by End-to-End, ImageNet, and VANP. VANP can extract multiple regions of interest for navigation without downstream navigation supervision compared to single salient regions by End-to-End and ImageNet pre-trained models.

Training a visual navigation-specific encoder from scratch requires a large amount of data, leading to high computational demands and extended training times <cit.>. To reduce this computational burden, most approaches use pre-trained vision models <cit.>. While these models provide a decent scene representation, they specialize in extracting salient features for vision tasks such as object classification and detection <cit.>. These features may not always align with what is crucial for navigation <cit.>. For example, following sidewalks, avoiding grass, or navigating around stairs and guardrails are essential for robots, but these features might not be captured by encoders trained for generic vision tasks. Consequently, pre-trained models, like those trained on ImageNet, can sometimes lead to navigation failures by focusing on irrelevant distractions <cit.>.

Self-Supervised Learning (SSL) <cit.> has shown success in various computer vision tasks by extracting general features adaptable to downstream tasks with/without fine-tuning. For instance, Deep Neural Networks (DNNs) can be trained to predict the rotation of an image <cit.> or to reconstruct an image from its corrupted/obstructed version <cit.>. By completing these pretext tasks, DNNs learn to extract meaningful features from the data, which can be used to solve downstream tasks such as image classification and object detection <cit.>.
However, a discrepancy exists between features extracted from generic models and those specifically needed for navigation. This leads us to ask the question: can we train visual encoders that extract only navigation-relevant features using self-supervision?

Considering both the success of SSL on a variety of computer vision tasks and the oftentimes mismatched features provided by generic SSL models for navigation tasks, we present Vision-Action Navigation Pretraining (VANP), a non-contrastive self-supervised approach that completely relies on a navigation-specific pretext task to train the visual encoder without the need for negative samples.

The core idea behind VANP is inspired by how humans navigate in crowded spaces. We do not need to pay attention to all the people and objects in the scene, but only the ones that affect our navigation trajectory. To this end, VANP embeds visual history, future actions, and visual goal as self-supervision signals and leverages Transformers with additional context tokens (inspired by Bert <cit.> and VisionTransformers <cit.>) to generate embeddings. Then, VANP utilizes VICReg <cit.> as the pretext objective function to maximize the mutual information between the embeddings. The trained visual encoder can therefore discard redundant features unnecessary for navigation and focus only on navigation-relevant regions. For example, Fig. <ref> shows the activation map of the last layer of ResNet-50 <cit.> trained with different methods. VANP learns navigation-relevant visual features with the help of our navigation-specific self-supervision signals.

Our experimental results suggest that VANP-extracted features trained on a dataset <cit.> that only contains 0.08% samples compared to ImageNet are as informative for a downstream navigation task as using ImageNet features.
The contributions of this work can be summarized as follows:

* An SSL framework to train a visual encoder for robotic navigation tasks;

* Insights into what is happening inside CNNs during navigation using different approaches; and

* A benchmark on short and long-term navigation interaction to show the performance of different approaches.

§ RELATED WORK

Recent advances in natural language processing and computer vision, particularly those driven by self-supervised learning (SSL), motivate our work. In this section, we first compare common SSL approaches and then categorize applications of SSL into two groups for robotics and review their related works.

Self-Supervised Learning: SSL has shown promising results in recent years by almost reaching the performance of supervised baselines <cit.>. Within SSL, two primary approaches have emerged: contrastive methods and information maximization methods. Both methodologies benefit from the use of the Siamese network architecture <cit.>. Contrastive methods <cit.> typically require large data batches and leverage loss functions designed to explicitly push dissimilar data points away from the representations of similar data. Consequently, the performance of these methods is highly dependent on the quality and quantity of negative samples <cit.>. Recent advancements have led to the development of contrastive approaches that do not necessitate negative samples for learning effective embeddings. These methods employ various strategies to achieve comparable performance, such as BYOL <cit.>, which utilizes a momentum encoder where one head receives a low-pass filtered version of the other. Alternatively, SimSiam <cit.> achieves similar results by halting gradient flow within one of the heads.

Information maximization methods such as BarlowTwins <cit.> maximize the information between two heads by enforcing the empirical cross-correlation between the embeddings of both heads to be equivalent to the identity matrix. Additionally, VICReg <cit.> incorporates regularization terms to prevent information collapse, particularly in scenarios involving multimodal data. Therefore, VANP leverages VICReg to learn visual features by maximizing the information between different modalities.

Pre-training for Better Representation: Codevilla et al. <cit.> demonstrated the value of pre-trained models for training better policies in autonomous vehicles. Subsequently, many works adopted pre-trained computer vision models, often trained on ImageNet <cit.>. However, general-purpose "foundation models" pre-trained on pretext tasks can achieve richer representations, enabling them to generalize to various downstream tasks with minimal data in a zero- or few-shot manner <cit.>.

The literature has extensively studied foundation models for robot manipulation <cit.>. For example, R3M <cit.> pre-trained a general visual encoder for manipulation tasks on the Ego4D human video dataset <cit.>, while CLIPort <cit.> leveraged the CLIP model <cit.> to enable language instructions for manipulation.  Dadashi et al. proposed AQuaDem <cit.>, a framework to learn quantized actions from demonstrations in continuous action spaces, while VANP is doing the opposite by learning visual features from continuous action spaces. Luo et al. <cit.> improved AQuaDem by using VQ-VAE <cit.> for offline reinforcement learning. Huang et al. <cit.> proposed Skill Transformer to learn long-horizon robotic tasks with the help of Transformers <cit.>.

Inspired by Taskonomy <cit.>, Shen et al. proposed conditioning visual demonstrations like segmentation and depth maps on actions during fusion rather than employing a naive fusion approach <cit.>. Yang et al. <cit.> projected the visual cues for navigation on the image space and then trained a policy on the augmented image. STERLING <cit.> and CAHSOR <cit.> have explored the concept of human preference learning and competence-awareness in the context of off-road navigation using SSL. These methods aligned sensor and visual embeddings by maximizing the mutual information between embeddings by leveraging VICReg <cit.> and BarlowTwins<cit.> respectively.

The work by Eftekhar et al. <cit.> presented the closest approach to VANP, employing a learnable codebook module to selectively filter visual observations based on the specific task. However, this approach inherently limits the model's generalization by relying on the downstream task. In contrast, VANP deliberately disregards such task-specific information, focusing instead on extracting general navigation-relevant features. Another work closely related to VANP is NavFormer <cit.>, which utilized BYOL <cit.> on two input images retrieved from a simulator. These images differ in the presence of dynamic objects within the scene. However, this approach confines NavFormer to the simulated environment, limiting its ability to generalize to real-world data. Conversely, VANP achieves real-world data generalization without relying on the pre-definition of specific rules only possible in simulation.

Pre-training for Better Policies:
Foundation models hold promise for learning not only rich representations but also policies that can generalize across robotic tasks. For instance, SayCan <cit.> integrates pre-trained language skills with robot actions, demonstrating the potential of pre-training for robotic tasks. This allows robots to physically execute tasks, while the language model provides high-level task insights. Evaluations of real-world robotic tasks confirm the effectiveness of this grounded approach in handling abstract, long-duration instructions for a mobile manipulator.  Li et al. <cit.> pre-trained language models to initialize policy networks predicting actions. Reid et al. <cit.> fine-tuned pre-trained sequence models on offline reinforcement learning tasks as the policy backbone. VPT <cit.> used pseudo-labeled Minecraft YouTube videos to learn a behavior cloning policy that can craft diamonds. VPT learns the inverse dynamics while VANP uses dynamics to learn visual features. GNM <cit.> learned a general policy to drive any robot by combining multiple datasets of different robot types. ViNT <cit.> further improved GNM by replacing the policy network with a Transformer <cit.>.

§ METHODOLOGY

VANP Architecture. VANP learns to embed temporal features into spatial features by using a sequence of images and leveraging two TransformerEncoders with context tokens by maximizing the mutual information between history, future actions, and the goal (left). Then, by appending an MLP to the Transformer context token, VANP predicts future trajectories during the downstream navigation task (right).

Learning visual features for robot navigation using only RGB camera input presents several challenges. Unlike traditional approaches that rely on LiDAR or depth cameras, RGB cameras lack explicit geometric information, making navigation more complex <cit.>. Here, we formally define the visual navigation task and the learning setting for Vision-Action Navigation Pre-training (VANP).

§.§ Problem Definition

We define visual navigation as the task of navigating an environment with only RGB camera input, as explored in previous works <cit.>. The visual navigation problem can be formalized as follows. Input: The robot is given a sequence of past and current images from its front-facing camera, $o_t = [I_{t-\tau_P}, I_{t-\tau_P + 1}, \ldots, I_t] \in \mathcal{O}$, where $t$ is the current time step, $\tau_P$ is the number of past frames, and $\mathcal{O}$ is the space of all possible image sequences. The robot is also given its current goal e.g., GPS coordinates, pose, image, or next local coordinate in 2D space, $g \in \mathcal{G}$, which determines the direction it should move in the next time step. Output: The robot must select an action $a_t \in \mathcal{A}$ consisting of continuous linear and angular velocities. $\mathcal{A} = [-1, 1]^2$ is the action space, where $[-1, 1]$ maps to the minimal and maximal linear and angular velocity of the robot. Visual Navigation: The goal is to learn a policy, $\pi_{\theta}: \mathcal{O} \times \mathcal{G} \rightarrow \mathcal{A}$, where $\theta$ represents the policy's parameters, to determine which action to take at each time step to reach its goal efficiently while avoiding collisions with others.

End-To-End models: For end-to-end or holistic models, we define the policy $\pi_{\theta}$ as follows: $a = \pi_{\theta}(o, g) = \sigma_{\zeta}(p_{\phi}(o) \oplus q_{\psi}(g))$, where $\sigma$ is the controller policy parametrized by $\zeta$, $p$ is the image encoder parameterized by $\phi$, $q$ is the goal encoder parameterized by $\psi$, and $\oplus$ is the aggregation of two vectors. To learn these parameters, two common approaches are (1) to learn all of them together in an end-to-end manner which makes the training difficult and time-consuming or (2) to pre-train the image encoder separately and only fine-tune the goal encoder along with the controller to reduce training time.

Challenges in visual feature learning: While extensive research has explored learning visual features for computer vision tasks using SSL <cit.>, adapting these models to specific tasks presents unique challenges <cit.>. Images in the real world contain implicit cues for navigation but are sometimes full of redundant information. In the context of visual navigation, one such challenge lies in learning visual features from image sequences without unnecessarily capturing such a redundancy, which may result in ambiguity. Additionally, it is not trivial to extract contrastive learning signals from visual navigation actions for contrastive SSL, e.g., an action appropriate for one scenario may or may not be appropriate for another, or different actions may be appropriate for the same scenario.  For instance, in a scenario where a pedestrian stands in front of the robot, two equally valid actions exist: overtaking from either the left or right side. In such cases, simply negating the angular velocity cannot yield a meaningful negative sample and can introduce ambiguity. Furthermore, employing actions from different sequences as negative samples might not provide pertinent information for visual navigation, as actions are inherently influenced by the observed environment. In the next section, we show how VANP addresses these challenges and trains the image encoder $p$ without a downstream objective function.

§.§ Vision-Action Model

VANP leverages VICReg <cit.> to maximize the information between past observations, a future goal, and future actions while maintaining the information collapse between input heads to train the image encoder $p$. Unlike vision SSL models that work on the joint embedding of augmented images <cit.>, VANP correlates the action space $\mathcal{A}$ and goal space $\mathcal{G}$ with the pixel latent space $\mathcal{O}$ as shown in Fig. <ref>. We define VANP pre-training as follows: We sample a batch of $(I^i_{t-\tau_P:t}, a^i_{t:t+\tau_F}, g^i_t)$ from dataset $\mathcal{D}$, where $i$ is the sample number, $I^i_{t-\tau_P:t}$ is a sequence of past visual observations starting from $t-\tau_P$ and ending at $t$, $a^i_{t:t+\tau_F}$ is a sequence of future actions starting from $t$ and ending at $t+\tau_F$, and $g^i_t$ is the current goal at time $t$ instantiated as an image in the future $I^i_{t+\tau_F}$. $\tau_F$ is the number of frames in the future and $\tau_P$ is the number of frames in the past. We then feed $I^i_{t-\tau_P:t}$ to $p_{\phi}$, typically a CNN, and all the embeddings to a transformer encoder <cit.>, as well as $a^i_{t:t+\tau_F}$ to $f_{\xi}$ as part of another transformer encoder, to learn image $Z^i$ and action $Z^a$ embeddings, respectively. Each transformer contains an additional context token to capture the continuous information among frames. We feed $g^i_t$ to $p_{\phi}$ to generate goal embedding $Z^g$. Finally, we use VANP's objective function to learn $\phi$ and $\xi$:

\begin{equation} \label{eq:loss1}
\begin{split}
\mathcal{L}_{\text{VANP}}(Z^i, Z^g, Z^a) &= \lambda \mathcal{L}_{\text{VICReg}}(Z^i, Z^g) \\
&+ (1 - \lambda) \mathcal{L}_{\text{VICReg}}(Z^i, Z^a),
\end{split}
\end{equation}

where $\lambda$ is the importance of each term,

and $\mathcal{L}_{\text{VICReg}}$ is the VICReg objective function <cit.> defined as:

\begin{equation} \label{eq:loss2}
\begin{split}
\small
\mathcal{L}_{\text{VICReg}}(Z^1, Z^2) &= \mu^1 s(Z^1, Z^2) \\
&+ \mu^2[v(Z^1) + v(Z^2)] \\
&+ \mu^3[c(Z^1) + c(Z^2)].
\end{split}
\end{equation}

$s$ is the distance between embedding spaces, $v$ and $c$ are the variance and covariance of each embedding respectively. $\mu^1$, $\mu^2$, and $\mu^3$ are hyper-parameters controlling the effectiveness of each term. Leveraging VICReg's objective function offers the advantage of circumventing the need for negative samples, which, as mentioned above, is challenging to define within the action space for navigation tasks.

§.§ Implementation Details

We implement VANP with PyTorch <cit.> and the training is performed on a single A5000 GPU with 24GB memory[ <https://github.com/mhnazeri/VANP>].

Model architecture: Considering the limited computation resources onboard most mobile robots, we choose ResNet-50 <cit.> without the classification head as a low-latency image encoder for $p_\phi$ and we call it VANP-50. We use two TransformerEncoders with additional context vectors <cit.> with four layers and four heads as the final image and action encoders to produce the embeddings of $Z^i, Z^a \in \mathbb{R}^{512}$. Both encoders are followed by MLPs with three layers as the projection heads to generate the final $Z'^i, Z'^a \in \mathbb{R}^{1024}$. We apply the same $p_\phi$ to the goal image to generate $Z^g \in \mathbb{R}^{512}$. A critical challenge arises from the inherent differences in modalities between the two networks generating the embeddings, leading to significant variations in their output ranges. To address this discrepancy and ensure effective integration, we initialize all deep networks using the Kaiming Normal initialization <cit.> with a mean of zero and a variance of one. In the context of the downstream model, an MLP is appended to the Transformer's context vector to predict trajectories at three and five seconds into the future, enabling the evaluation of how the extracted features influence both short-term and long-term interactions.

Optimization: We use the ADAMW optimizer <cit.> and train the model for 200 epochs with a batch size of 128 and a learning rate of $5e^{-4}$. To ensure a fair comparison, all models are trained for 50 epochs using the same optimizer and hyperparameters during downstream training. The sole exception is the end-to-end model, which requires 100 epochs to guarantee convergence.

Dataset: We leverage a selection of two unique datasets: SCAND <cit.> and MuSoHu <cit.>, both of which encapsulate robot and human navigation data from the egocentric perspective. Both real-world datasets are collected in a variety of natural crowded public spaces. MuSoHu comprises approximately 20 hours of data captured from human egocentric motion. The recordings capture human walking patterns in public spaces, providing insights for learning human-like, socially compliant navigation behaviors. SCAND is an autonomous robot navigation dataset that captures 8.7 hours of human-teleoperated robot navigation demonstrations in naturally crowded public spaces on a university campus. To minimize data ambiguity and noise, a subset of the two datasets are carefully curated, resulting in a dataset of approximately 11,000 samples, which are used for both pre-training and training. Additionally, a separate set of 8,000 unseen samples are used for downstream navigation task evaluation. For pretext task training, we set $\tau_P$ and $\tau_F$ to 6 and 20 respectively and use a sequence of images $I_{t-\tau_P +1:t} \in \mathbb{R}^{\tau_P \times 98 \times 126}$ along with a goal image $g_t \in \mathbb{R}^{98 \times 126}$ and a sequence of actions $a_{t:t + \tau_F -1} \in \mathbb{R}^{\tau_F \times 2}$ parsed at 4 Hz, comprising of 1.5 seconds in the past and 5 seconds in the future. For the downstream task, we use a sequence of past observations $I_{t - \tau_P +1: t} \in \mathbb{R}^{\tau_P \times 98 \times 126}$ along with the polar coordinates of the next local goal $g \in \mathbb{R}^{2}$ parsed at 4 Hz, containing 1.5 seconds history as the network input to produce the actions $\mathcal{A}_{t:t + \tau_F -1} \in \mathbb{R}^{\tau_F \times 2}$ for three and five seconds in the future.

§ EXPERIMENTAL RESULTS

We provide experimental results using VANP compared against a ResNet-50 pre-trained on ImageNet and end-to-end from scratch as baselines.

§.§ Results Discussion

We assess the efficacy of VANP pretext training by quantitatively comparing its performance with that of a ResNet-50 model <cit.> pre-trained on the ImageNet ILSVRC-2012 dataset <cit.>. This serves as the baseline alongside another ResNet-50 model trained end-to-end with randomly initialized weights. To guarantee a fair comparison, the architectures of all other components within the downstream task remain unchanged. Table <ref> presents the mean squared error between the predicted and ground truth trajectories for short- (three seconds) and long-term (five seconds) interactions under two conditions. In the first condition, only the goal encoder and controller are trained during the downstream navigation task, while the image encoder weights are frozen. In the second condition, we compare the performance by unfreezing the image encoder weights to enable fine-tuning.

The results in Table <ref> demonstrate that VANP achieves comparable performance to the end-to-end trained model while requiring only half the training time. Furthermore, VANP pre-trained model achieves comparable performance to ImageNet model with only 0.08% of the data size required by ImageNet, highlighting how informative the extracted representations are for navigation.

When provided with a sequence of past observations, VANP exhibits a superior ability (0.383) to utilize this additional data compared to ImageNet model when frozen (0.435). Although the ImageNet weights appear unable to leverage the temporal features provided by the transformer component when freezing its weights (Table <ref>, row four compared against row three), fine-tuning the ImageNet model leads to performance improvement from 0.435 to 0.292, suggesting that it can better capture underlying temporal features provided by the Transformer through fine-tuning.

However, we do not see such an improvement in the case of VANP. The negligible improvement in accuracy from 0.383 to 0.338 for VANP during fine-tuning can be attributed to two reasons. First, the focus on multiple navigation-related visual regions of VANP's pre-trained weights (Fig. <ref> last row) impedes adaptation/forgetting during fine-tuning compared to the ImageNet weights. Second, the temporal features from the Transformer are already in VANP weights and therefore does not require much fine-tuning. Overall, it is likely that forgetting/updating weights can be easier when the visual encoder is trained using only one single scalar instructive feedback (i.e., training loss) rather than pre-trained on richer instructive signals, i.e., VANP's pre-training objective signal.

Interestingly, during frozen evaluation with only one image as input, the frozen pre-trained ImageNet model (Table <ref>, row three) achieves the best performance. This finding warrants further investigation. One assumption is that in test cases, the salient object has a stronger influence on the trajectory and aligns better with the single, scalar form of instructive feedback provided. However, during fine-tuning, it is clear that the single image does not outperform models utilizing Transformer temporal features (0.342) while the VANP model benefits from these features even with only one image as input (0.315).

Visual inspection of the learned activation maps on the last layer of ResNet-50 (Fig. <ref>) reveals distinct characteristics across the models. The last row on Fig. <ref> shows that the VANP pre-trained model exhibits activation maps with a higher degree of relevance to navigation tasks, focusing on features such as paths and obstacles while the ImageNet pre-trained model (Fig. <ref> third row) primarily focuses on salient objects within the environment, which might not be directly related to navigation. Another difference between VANP and the end-to-end model (Fig. <ref> second row) is that the end-to-end model tends to concentrate on a single critical region significantly impacting the trajectory, likely due to its limited instructive signal during training, i.e., minimizing the distance between predicted and ground truth trajectories. Conversely, VANP demonstrates the ability to extract information from multiple regions, potentially benefiting from the richer information provided by the goal image and future actions during the pre-training stage. However, as mentioned above, this richness impedes adaptation during fine-tuning.

We observe instances where the attention of all models shifts to seemingly irrelevant aspects. In the case of VANP, we posit that this may be due to the robot's sharp turns temporarily obscuring the goal image from the current frame.

Qualitative Comparison. Comparison of the last layer activation maps among different methods on unseen scenarios.

§.§ Ablations

To investigate the most effective approach for correlating visual and action spaces, we conduct a series of ablation studies, in which we report the mean squared distance of the predicted trajectory from the ground truth in three and five seconds in the future in Table <ref>.

Role of Different Training Signals: We assessed the individual contributions of various self-supervised training signals by changing the value of $\lambda$ between 0 and 1 in Eq. <ref>. Our findings reveal that while action signals provide valuable navigational cues, their sparsity often hinders their effectiveness in downstream navigation tasks, especially during long-term interactions. Conversely, information derived from the goal, while occasionally exhibiting redundancy, improved performance from 0.499 to 0.392 during long-term interactions over using only actions due to informative cues alongside the redundant elements. However, this redundancy poses challenges for the policy network, which can be remedied by more training epochs and a deeper policy network. By combining these two embeddings as the self-supervision signal, the final model can effectively learn informative features while mitigating the impact of redundant information within the embedding.

Leveraging Goal Information: We further investigated the optimal utilization of future goal information. Our findings suggest that employing the goal solely as a supervision signal (shown as Actions+GoalOut in Table <ref>) proves more effective in facilitating the model's learning of visual features compared to incorporating the goal directly within the Transformer architecture (shown as Actions+GoalIn in Table <ref>). The Transformer's ability to capture temporal changes from the current to the goal frame is only helpful when the goal is visible from the current frame.

§.§ Limitations

We identify multiple key limitations of the VANP pre-training approach. First, our analysis of the learned kernels suggests that VANP performs more effectively when the goal image is directly visible from the current image, likely due to its reliance on image correlation for learning. This observation highlights a potential limitation in generalizability to scenarios where the goal location may not be directly visible from the starting point. Second, in large-scale datasets likely with a significant amount of noise, scaling VANP poses a potential challenge, considering its need for high-quality self-supervision during pre-training can result in many changes in learned activation maps between epochs. Additionally, our current findings are based on a static dataset and may not directly translate to challenging real-world navigation tasks that involve dynamic environments and unforeseen obstacles. Addressing these limitations and exploring the application of VANP in real-world scenarios are key areas for future work.

§ CONCLUSIONS AND FUTURE WORK

In this work, we propose a self-supervised learning approach to train visual encoder models specifically designed for visual navigation. This approach is motivated by the observation that humans only pay attention to specific navigation-relevant regions of their frontal view to efficiently make navigation decisions. By reversing this observation, we use the navigation decisions to extract only visual features that are relevant to the navigation task, unlike computer vision models that mainly extract salient details, which are potentially irrelevant to navigation tasks and can therefore lead to confusion for neural-based controllers. To achieve this, we leverage two Transformer Encoders to embed past visual observation, future actions, and a goal image, then we maximize the information between these embeddings using VANP's objective function to learn visual backbone weights.

In the future, we plan to conduct more real-world experiments and scale up the model to larger datasets.
Another future direction is to merge datasets from different environments, such as indoor <cit.>, outdoor <cit.>, off-road <cit.>, and social environments <cit.>, to extend the generalizability of the proposed VANP approach.


Wolfgang Mulzer and Jeff M. Phillips 2 40th International Symposium on
Computational Geometry (SoCG 2024) SoCG 2024 SoCG 2024 June 11-14, 2024
Athens, Greece socg-logo 293 XX Department of Computer Science and
Engineering, Tandon School of Engineering, New York University, Brooklyn, NY
11201 USA and https://engineering.nyu.edu/faculty/boris-
aronovboris.aronov@nyu.eduhttps://orcid.org/0000-0003-3110-4702Work has been
supported by NSF grant CCF 20-08551. Department of Mathematics and Computer
Science, TU Eindhoven, the
NetherlandsM.T.d.Berg@tue.nlhttps://orcid.org/0000-0001-5770-3784MdB is
supported by the Dutch Research Council (NWO) through Gravitation-grant
NETWORKS-024.002.003. Department of Mathematics and Computer Science, TU
Eindhoven, the
Netherlandsl.theocharous@tue.nlhttps://orcid.org/0000-0002-1707-6787LT is
supported by the Dutch Research Council (NWO) through Gravitation-grant
NETWORKS-024.002.003. Boris Aronov, Mark de Berg, and Leonidas Theocharous
[100]Theory of computation Design and analysis of algorithms A preliminary
version of this work will appear in _SoCG’24_[4]

# A Clique-Based Separator for Intersection Graphs of Geodesic Disks in
$\Reals^{2}$

Boris Aronov  Mark de Berg  Leonidas Theocharous

###### Abstract

Let $d$ be a (well-behaved) shortest-path metric defined on a path-connected
subset of $\Reals^{2}$ and let $\mathcal{D}=\\{D_{1},\ldots,D_{n}\\}$ be a set
of geodesic disks with respect to the metric $d$. We prove that
$\mathcal{G}^{\times}(\mathcal{D})$, the intersection graph of the disks in
$\mathcal{D}$, has a clique-based separator consisting of
$O(n^{3/4+\varepsilon})$ cliques. This significantly extends the class of
objects whose intersection graphs have small clique-based separators.

Our clique-based separator yields an algorithm for $q$-Coloring, which runs in
time $2^{O(n^{3/4+\varepsilon})}$, assuming the boundaries of the disks
$D_{i}$ can be computed in polynomial time. We also use our clique-based
separator to obtain a simple, efficient, and almost exact distance oracle for
intersection graphs of geodesic disks. Our distance oracle uses
$O(n^{7/4+\varepsilon})$ storage and can report the hop distance between any
two nodes in $\mathcal{G}^{\times}(\mathcal{D})$ in $O(n^{3/4+\varepsilon})$
time, up to an additive error of one. So far, distance oracles with an
additive error of one that use subquadratic storage and sublinear query time
were not known for such general graph classes.

###### keywords:

Computational geometry, intersection graphs, separator theorems

##  1 Introduction

#### (Clique-based) separators.

The Planar Separator Theorem states that any planar graph with $n$ nodes has a
_balanced separator_ of size $O(\sqrt{n})$. In other words, for any planar
graph $\mathcal{G}=(V,E)$ there exists a subset $S\subset V$ of size
$O(\sqrt{n})$ with the following property:111Hereafter we will simply refer to
such a subset as a _separator_ , omitting the word “balanced” for brevity.
Moreover, we do not require the balance factor to be 2/3, but we allow the
size of the subsets $A$ and $B$ to be at most $\delta n$, for some fixed
constant $\delta<1$.  $V\setminus S$ can be split into subsets $A$ and $B$
with $|A|\leqslant 2n/3$ and $|B|\leqslant 2n/3$ such that there are no edges
between $A$ and $B$. This fundamental result was first proved in 1979 by
Lipton and Tarjan [20] and has been simplified and refined in several ways,
see, e.g., [12, 13]. The Planar Separator Theorem proved to be extremely
useful for obtaining efficient divide-and-conquer algorithms for a large
variety of problems on planar graphs.

In this paper we are interested in _geometric intersection graphs_ in the
plane. These are graphs whose node set corresponds to a set $\mathcal{D}$ of
objects in the plane and that have an edge between two nodes iff the
corresponding objects intersect. We will denote this intersection graph by
$\mathcal{G}^{\times}(\mathcal{D})$. _(Unit) disk graphs_ and _string graphs_
—where the set $\mathcal{D}$ consists of (unit) disks and curves,
respectively—are among the most popular types of intersection graphs. Unit
disk graphs in particular have been studied extensively, because they serve as
a model for wireless communication networks. It is well known that disk graphs
are generalizations of planar graphs, because by the Circle Packing Theorem
(also known as the Koebe–Andreev–Thurston Theorem) every planar graph is the
intersection graph of a set of disks with disjoint interiors [25]. It is
therefore natural to try to extend the Planar Separator Theorem to
intersection graphs. A direct generalization is clearly impossible, however,
since intersection graphs can contain arbitrarily large cliques.

There are several ways to still obtain separator theorems for intersection
graphs. One can allow the size of the separator to depend on $m$, the number
of edges, instead of on the number of vertices. For example, any string graph
admits a separator of size $O(\sqrt{m})$ [18]. One may also put restrictions
on the set $\mathcal{D}$ to prevent large cliques. For example, if we restrict
the _density_ 222The density of a set $\mathcal{D}$ of objects in $\Reals^{d}$
is the maximum, over all balls $b\subset\Reals^{d}$, of the cardinality of the
sets $\\{o\in\mathcal{D}:o\cap b\neq\emptyset\mbox{ and
}\mathrm{diam}(o)\geqslant\mathrm{diam}(b)\\}$, where $\mathrm{diam}(o)$
denotes the diameter of object $o$. of a set $\mathcal{D}$ of planar objects
to some value $\lambda$, then we can obtain a separator333The result
generalizes to $\Reals^{d}$, where the bound becomes
$O(\lambda^{1/d}n^{1-1/d})$. of size $O(\sqrt{\lambda n})$ [16]. This result
implies that intersection graphs of disks (or, more generally, of _fat_
objects) whose ply is bounded by a constant admit a separator of size
$O(\sqrt{n})$. (The _ply_ of a set of objects in $\Reals^{2}$ is the maximum,
over all points $q\in\Reals^{2}$, of the number of objects containing $q$.)
Recently, De Berg et al. [10], following work of Fu [14], introduced what we
will call _clique-based separators_. A clique-based separator is a (balanced)
separator consisting of cliques, and its size is not measured as the total
number of nodes of the cliques, but as the number of cliques. De Berg et
al.showed that the intersection graph of a set $\mathcal{D}$ of convex fat
object in the plane admits a separator consisting of $O(\sqrt{n})$ cliques. In
fact, their result is slightly stronger: it states that there is a separator
$S$ that can be decomposed into $O(\sqrt{n})$ cliques $C_{1},\ldots,C_{t}$
such that $\sum_{i=1}^{t}\gamma(|C|)=O(\sqrt{n})$, where $\gamma(t)=\log t$ is
a cost function444In fact, the result holds for any cost function
$\gamma(t)=O(t^{\frac{1}{2}-\varepsilon})$, where $\varepsilon>0$ is a
constant, but in typical applications either only the number of cliques is
important, or $\gamma(t)=\log t$ suffices. on the cliques. Clique-based
separators are useful because cliques can be handled very efficiently for many
problems. De Berg et al.used their clique-based separators to develop a
unified framework to solve many classic graph problems, including Independent
Set, Dominating Set, Feedback Vertex Set, and more.

Recently De Berg et al. [11] proved clique-based separator theorems for
various other classes of objects, including map graphs and intersection graphs
of pseudo-disks, which admit clique-based separators consisting of
$O(\sqrt{n})$ and $O(n^{2/3})$ cliques, respectively. They also showed that
intersection graphs of _geodesic disks inside a simple polygon_ —that is,
geodesic disks induced by the standard shortest-path metric inside the
polygon—admit a clique-based separator consisting of $O(n^{2/3})$ cliques.
They left the case of geodesic disks in a polygon with holes as an open
problem. We note that string graphs, which subsume the class of intersection
graphs of geodesic disks, do _not_ admit clique-based separators of sublinear
size, since string graphs can contain arbitrarily large induced bipartite
cliques.

#### Our results.

In this paper we show that intersection graphs of geodesic disks in a polygon
with holes admit a clique-based separator consisting of a sublinear number of
cliques. Our result is actually much more general, as it shows that _for any
well-behaved shortest-path metric $d$_ defined on a path-connected and closed
subset $F\subset\Reals^{2}$, a set of geodesic disks with respect to that
metric admits a separator consisting of $O(n^{3/4+\varepsilon})$ cliques. This
includes the shortest-path metric defined by a set of (possibly curved)
obstacles in the plane, the shortest-path metric defined on a terrain, and the
shortest-path metric among weighted regions in the plane. (See Section 2.3 for
the formal requirements on a well-behaved shortest-path metric.) Note that we
do not require shortest paths to be unique, nor do we put a bound on the
number of intersections between the boundaries of two geodesic disks, nor do
we require the metric space to have bounded doubling dimension.

The generality of our setting implies that previous approaches to construct
clique-based separators will not work. For example, the method of De Berg et
al. [10] to construct a clique-based separator for Euclidean disks crucially
relies on disks being fat objects. More precisely, it uses the fact that many
relatively large fat objects intersecting a given square must form $O(1)$
cliques. This property already fails for geodesic disks for the Euclidean
shortest-path metric inside a simple polygon. Thus, De Berg et al. [11] use a
different approach: they prove that geodesic disks inside a simple polygon are
_pseudo-disks_ and then show how to obtain a clique-based separator for
pseudo-disks. In our more general setting, however, geodesic disks need not be
pseudo-disks: the boundaries of two geodesic disks in an arbitrary metric can
intersect arbitrarily many times—this is already the case for the Euclidean
shortest-path metric in a polygon with holes. Thus we have to proceed
differently.

The idea of our new approach is as follows. We first reduce the ply of the set
$\mathcal{D}$ by removing all cliques of size $\Omega(n^{1/5})$, thus
obtaining a set $\mathcal{D}^{*}$ of ply $O(n^{1/5})$. (The removed cliques
will eventually be added to the separator. A similar preprocessing step to
reduce the ply was used in [11] to handle pseudo-disks.) The remaining
arrangement can still be arbitrarily complex, however. To overcome this, we
ignore the arrangement induced by the disks, and instead focus on the
realization of the graph $\mathcal{G}^{\times}(\mathcal{D}^{*})$ obtained by
drawing a shortest path $\pi_{ij}$ between the centers of any two intersecting
disks $D_{i},D_{j}\in\mathcal{D}^{*}$. We then prove that the number of edges
of $\mathcal{G}^{\times}(\mathcal{D}^{*})$ must be $O(n^{8/5})$; otherwise
there will be an intersection point of two shortest paths
$\pi_{ij},\pi_{k\ell}$ that has large ply, which is not possible due to the
preprocessing step. Since the number of edges of
$\mathcal{G}^{\times}(\mathcal{D}^{*})$ is $O(n^{8/5})$ we can use the
separator result on string graphs to obtain a separator of size
$O(\sqrt{n^{8/5}})=O(n^{4/5})$. Adding the cliques that were removed in the
preprocessing step then yields a separator consisting of $O(n^{4/5})$ cliques
and singletons. Finally, we devise a bootstrapping mechanism to further
decrease the size of the separator, leading to a separator consisting of
$O(n^{3/4+\varepsilon})$ cliques.

Clique-based separators give sub-exponential algorithms for Maximum
Independent Set, Feedback Vertex Set, and $q$-Coloring for constant $q$ [11].
When using our clique-based separator, the running times for Maximum
Independent Set and Feedback Vertex Set are inferior to what is known for
string graphs. For $q$-Coloring with $q\geqslant 4$ this is not the case,
however, since $4$-Coloring does not admit a sub-exponential algorithm,
assuming eth [5]. Our clique-based separator, on the other hand, yields an
algorithm with running time $2^{O(n^{3/4+\varepsilon})}$, assuming the
boundaries of the disks $D_{i}$ can be computed in polynomial time. Another
application of our separator result is to distance oracles, as discussed next.

#### Application to distance oracles.

One of the most basic queries one can ask about a (possibly edge-weighted)
graph $G=(V,E)$ is a _distance query_ : given two nodes $s,t\in V$, what is
the distance between them? A data structure answering such queries is called a
_distance oracle_. One can simply store all pairwise distances in a distance
matrix so that distance queries can be answered in $O(1)$ time, but this
requires $\Theta(n^{2})$ storage, where $n\coloneq|V|$. At the other extreme,
one can do no preprocessing and answer a query by running a single-source
shortest path algorithm; this uses $O(n+m)$ storage, where $m\coloneq|E|$ and
a query costs $\Omega(n)$ time. The main question is if sublinear query time
can be achieved with subquadratic storage.

As an application of our clique-based separator we present a simple and almost
exact distance oracle for intersection graphs of geodesic disks. While our
approach is standard—it was already used in 1996 by Arikati et al. [3]—it does
provide an almost exact distance oracle in a more general setting than what
was known before, thus showing the power of clique-based separators. Our
distance oracle uses $O(n^{7/4+\varepsilon})$ storage and can report the hop
distance between any two nodes in $\mathcal{G}^{\times}(\mathcal{D})$ in
$O(n^{3/4+\varepsilon})$ time, up to an additive error of one. This is the
first distance oracle with only an additive error for a graph class that is
more general than planar graphs: even for Euclidean unit-disk graphs the known
distance oracle has a multiplicative error [6, 15]. (Admittedly, the storage
and query time of this oracle are significantly better than of ours.) We note
that clique-based separators were recently also used (in a similar way) to
obtain a distance oracle for so-called transmission graphs [9]. (A
transmission graph is a directed graph whose nodes correspond to Euclidean
disks in the plane, and that have an edge from disk $D_{i}$ to disk $D_{j}$
iff the center of $D_{j}$ is contained in $D_{i}$.)

#### Related work on distance oracles.

There has been a lot of work on distance oracles, both for undirected and for
directed graphs; see for example the survey by Sommer [23] for an overview of
the work up to 2014. Since our interest is in intersection graphs, which are
undirected, hereafter we will restrict our discussion to undirected graphs.

In the edge-weighted setting, one obviously needs to store all edge weights to
answer queries exactly. Hence, for exact distance oracles on weighted graphs
the focus has been on on sparse graphs and, in particular, on planar graphs.
Very recently, Charalampopoulos et al. [7] achieved a major breakthrough by
providing an exact distance oracle for planar graphs that uses $O(n^{1+o(1)})$
storage and has $O(\log^{2+o(1)})$ query time. The solution even works for
weighted planar graphs, and it allows other trade-offs as well. For
$(1+\varepsilon)$-approximate distance oracles on planar graphs, Le and Wulff-
Nilsen [17] showed how to achieve $O(1/\varepsilon^{2})$ query time with
$O(n/\varepsilon^{2})$ storage. We refer the reader to the recent paper by
Charalampopoulos et al. [7] for a historical overview of the results on planar
distance oracles.

For non-planar graphs the results are far less good: the distance oracles are
approximate and typically use significantly super-linear storage; see the
survey by Sommer [23]. For example, Chechik [8] presented a
$(2k-1)$-approximate distance oracle using $O(kn^{1+1/k})$ storage and with
$O(1)$ query time, for any given integer $k\geqslant 1$. Moreover, for
$t<2k-1$, any $t$-approximate distance oracle requires $\Omega(kn^{1+1/k})$
bits of storage [24].

Somewhat better results are known for unweighted graphs, where the
approximation often has an additive term in addition to the multiplicative
term. More precisely, if $d_{G}(s,t)$ denotes the actual distance between $s$
and $t$ in $G$, then an _$(\alpha,\beta)$ -approximate oracle_ reports a
distance $d^{*}$ such that $d_{G}(s,t)\leqslant d^{*}\leqslant\alpha\cdot
d_{G}(s,t)+\beta$. Patrascu and Roditty [22] presented a $(2,1)$-approximate
oracle with $O(1)$ query time that uses $O(n^{5/3})$ storage, Abraham and
Gavoille [1] presented a $(2k-2,1)$-approximate oracle with $O(k)$ query time
that uses $\tilde{O}(n^{1+2/(2k-1)})$ storage (for $k\geqslant 2$).

To summarize, for non-planar graphs all distance oracles with subquadratic
storage have a multiplicative error of at least 2, even in the unweighted
case. The only exception is for the rather restricted case of unit-disk
graphs, where Gao and Zhang [15], and later Chan and Skrepetos [6], presented
a $(1+\varepsilon)$-approximate distance oracle with $O(1)$ query time that
uses $O_{\varepsilon}(n\log n)$ storage. (This result actually also works in
the weighted setting, where the weight of an edge between two disks is the
Euclidean distance between their centers.)

##  2 A clique-based separator for geodesic disks in $\Reals^{2}$ℝ²

Let $d$ be a metric defined on a closed path-connected subset
$F\subset\Reals^{2}$, and let $\mathcal{D}=\\{D_{1},\ldots,D_{n}\\}$ be a set
of geodesic disks in $F$, with respect to the metric $d$. Thus each
disk555From now on, to simplify the terminology, we omit the adjective
_geodesic_ and simply use the term _disk_ to refer to the objects in
$\mathcal{D}$. $D_{i}$ is defined as $D_{i}\coloneq\\{q\in
F:d(q,p_{i})\leqslant r_{i}\\}$, where $p_{i}\in F$ is the center of $D_{i}$
an $r_{i}\geqslant 0$ is its radius. Let $\mathcal{D}_{0}\coloneq\mathcal{D}$
and recall that $\mathcal{G}^{\times}(\mathcal{D}_{0})$ denotes the
intersection graph of $\mathcal{D}_{0}$. (The reason for introducing the
notation $\mathcal{D}_{0}$ will become clear shortly.) We denote the set of
edges of $\mathcal{G}^{\times}(\mathcal{D}_{0})$ by $E$ and define
$m\coloneq|E|$.

###  2.1 A first bound

Our basic construction of a clique-based separator $\mathcal{S}$ for
$\mathcal{G}^{\times}(\mathcal{D}_{0})$, yields a separator with $O(n^{4/5})$
cliques. In Section 2.2, we will apply a bootstrapping scheme to further
reduce the size of the separator. The basic construction proceeds in three
steps: in a preprocessing step we reduce the ply of the set of disks we need
to deal with, in the second step we prove that if the ply is sublinear then
the number of edges in the intersection graph is subquadratic, and in the
third step we construct the separator.

Step 1: Reducing the ply. For a point $p\in F$, let
$\mathcal{D}_{0}(p)\coloneq\\{D_{i}\in\mathcal{D}_{0}:p\in D_{i}\\}$ be the
set of disks from $\mathcal{D}_{0}$ containing $p$—note that
$\mathcal{D}_{0}(p)$ forms a clique in
$\mathcal{G}^{\times}(\mathcal{D}_{0})$—and define
$\operatorname{ply}(p)\coloneq|\mathcal{D}_{0}(p)|$ to be the ply of $p$ with
respect to $\mathcal{D}_{0}$. The ply of the set $\mathcal{D}_{0}$ is defined
as $\operatorname{ply}(\mathcal{D}_{0})\coloneq\max\\{p\in
F:\operatorname{ply}(p)\\}$.

We start by reducing the ply of $\mathcal{D}_{0}$ in the following greedy
manner. Let $\alpha$ be a fixed constant with $0<\alpha<1$. In the basic
construction we will use $\alpha=1/5$, but in our bootstrapping scheme we will
work with other values as well. We check whether there exists a point $p$ such
that $|\mathcal{D}_{0}(p)|\geqslant\frac{1}{4}n^{\alpha}$. If so, we remove
$\mathcal{D}_{0}(p)$ from $\mathcal{D}_{0}$ and add it as a clique to
$\mathcal{S}$. We repeat this process until
$\operatorname{ply}(\mathcal{D}_{0})<\frac{1}{4}n^{\alpha}$. Thus in the first
step at most $4n^{1-\alpha}$ cliques are added to $\mathcal{S}$.

To avoid confusion with our initial set $\mathcal{D}_{0}$, we denote the set
of disks remaining at the end of Step 1 by $\mathcal{D}_{1}$ and we denote the
set of edges of $\mathcal{G}^{\times}(\mathcal{D}_{1})$ by $E_{1}$.

Step 2: Bounding the size of $E_{1}$. To bound the size of $E_{1}$, we draw a
shortest path $\pi_{ij}$ between the centers $p_{i},p_{j}$ of every two
intersecting disks $D_{i},D_{j}\in\mathcal{D}_{1}$, thus obtaining a geometric
realization of the graph $\mathcal{G}^{\times}(\mathcal{D}_{1})$. From now on,
with a slight abuse of notation, we will not distinguish between an edge
$(D_{i},D_{j})$ in $\mathcal{G}^{\times}(\mathcal{D}_{1})$ and its geometric
realization $\pi_{ij}$. Let
$\Pi(\mathcal{D}_{1})\coloneq\\{\pi_{ij}:(D_{i},D_{j})\in E_{1}\\}$ be the
resulting set of paths. To focus on the main idea behind our proof we will,
for the time being, assume that $\Pi(\mathcal{D}_{1})$ is a _proper path set_
: a set of paths such that any two paths $\pi_{ij},\pi_{k\ell}$ have at most
two points in common, each intersection point is either a shared endpoint or a
proper crossing, and no proper crossing coincides with another proper crossing
or with an endpoint. When $\pi_{ij}$ and $\pi_{k\ell}$ have a proper crossing,
we say that they _cross_ , otherwise they do not cross.

We need the following well-known result about the number of crossings in dense
graphs, known as the Crossing Lemma [2, 19]. The term _planar drawing_ in the
Crossing Lemma refers to a drawing where no edge interior passes through a
vertex and all intersections are proper crossings. Thus it applies to a proper
path set.

######  Lemma 2.1 (Crossing Lemma).

There exists a constant $c>0$, such that every planar drawing of a graph with
$n$ vertices and $m\geqslant 4n$ edges contains at least
$c\frac{m^{3}}{n^{2}}$ crossings.

Using the Crossing Lemma we will show that
$|E_{1}|=O(n^{\frac{3+\alpha}{2}})$, as follows. If
$|E_{1}|=O(n^{\frac{3+\alpha}{2}})$ does not hold, then by the Crossing Lemma
there must be many crossings between the edges $\pi_{ij}\in E_{1}$. We will
show that this implies that there is a crossing of ply greater than
$\frac{1}{4}n^{\alpha}$, thus contradicting that
$\operatorname{ply}(\mathcal{D}_{1})<\frac{1}{4}n^{\alpha}$. We now make this
idea precise.

######  Lemma 2.2.

Let $\mathcal{G}^{\times}(\mathcal{D}_{1})=(\mathcal{D}_{1},E_{1})$ be the
intersection graph of a set $\mathcal{D}_{1}$ of disks such that
$\operatorname{ply}(\mathcal{D}_{1})<\frac{1}{4}n^{\alpha}$. Then
$|E_{1}|\leqslant\sqrt{\frac{4}{c}}\cdot n^{\frac{3+\alpha}{2}}$, where $c$ is
the constant appearing in the Crossing Lemma.

Figure 1: (i) An example of a labeling for a crossing $x\in\mathcal{X}$. (ii)
Here, the crossing $y\in\pi_{ij}[x,m_{k\ell}]$ is assigned to $D_{i}$ a total
of four times.

######  Proof 2.3.

Consider the proper path set $\Pi(\mathcal{D}_{1})$ and let $\mathcal{X}$ be
the set of crossings between the paths in $\Pi(\mathcal{D}_{1})$. Assume for a
contradiction that $|E_{1}|>\sqrt{\frac{4}{c}}\cdot n^{\frac{3+\alpha}{2}}$.
We will show that then there has to exist a crossing $x\in\mathcal{X}$ of ply
at least $\frac{n^{\alpha}}{4}$, which contradicts that
$\operatorname{ply}(\mathcal{D}_{1})<\frac{1}{4}n^{\alpha}$.

We start by giving a lower bound on the total ply of all crossings in the
drawing. To this end, we split each edge $\pi_{ij}\in E_{1}$ in two _half-
edges_ as follows. For two points $x,y\in\pi_{ij}$, let $\pi_{ij}[x,y]$ denote
the subpath of $\pi_{ij}$ between $x$ and $y$. Recall that $p_{i}$ is the
center of disk $D_{i}$. We now pick an arbitrary point
$m_{ij}\in\pi_{ij}\cap\left(D_{i}\cap D_{j}\right)$ and split $\pi_{ij}$ at
$m_{ij}$ into a half-edge $\pi_{ij}[p_{i},m_{ij}]$ connecting $p_{i}$ to
$m_{ij}$ and a half-edge $\pi_{ij}[p_{j},m_{ij}]$ connecting $p_{j}$ to
$m_{ij}$. For brevity, we will denote these two half-edges by $h_{ij}$ and
$h_{ji}$, respectively. Clearly, each half-edge has length at most the radius
of the disk it lies in, and so $h_{ij}\subset D_{i}$ and $h_{ji}\subset
D_{j}$. We denote the resulting set of half-edges by $\mathcal{E}_{1}$.

We label each crossing $x\in\mathcal{X}$ with an unordered pair of integers
$\\{\lambda_{1}(x),\lambda_{2}(x)\\}$, defined as follows: if $x$ is the
crossing between the half-edges $h_{ij},h_{k\ell}$, then $\lambda_{1}(x)$ is
the number of crossings contained in $\pi_{ij}[x,m_{ij}]$ and $\lambda_{2}(x)$
is the number of crossings contained in $\pi_{k\ell}[x,m_{k\ell}]$; see Fig.
1(i). This labeling is useful to obtain a rough bound on the total ply of all
crossings, because of the following observation, which immediately follows
from the triangle inequality.

  * _Observation 1._ Consider a crossing $x=h_{ij}\cap h_{k\ell}$. If $d(x,m_{k\ell})\leqslant d(x,m_{ij})$ then all crossings $y\in\pi_{k\ell}[x,m_{k\ell}]$ are contained in $D_{i}$, and otherwise all crossings $y\in\pi_{ij}[x,m_{ij}]$ are contained in $D_{k}$.

Let $K\coloneq\sum_{x\in\mathcal{X}}\operatorname{ply}(x)$ denote the total
ply of all crossings. The following claim bounds $K$ in terms of the labels
$\\{\lambda_{1}(x),\lambda_{2}(x)\\}$.

  * _Claim 1._ $K>\frac{1}{2|\mathcal{D}_{1}|}\sum_{x\in\mathcal{X}}\min\\{\lambda_{1}(x),\lambda_{2}(x)\\}$.

  * _Proof._ Define $K(D_{i})\coloneq\left|\\{x\in\mathcal{X}:x\in D_{i}\\}\right|$ to be the contribution of $D_{i}$ to the total ply $K$, and note that

$K=\sum_{x\in\mathcal{X}}\operatorname{ply}(x)=\sum_{x\in\mathcal{X}}\left|\\{D_{i}\in\mathcal{D}_{1}:x\in
D_{i}\\}\right|=\sum_{D_{i}\in\mathcal{D}_{1}}\left|\\{x\in\mathcal{X}:x\in
D_{i}\\}\right|=\sum_{D_{i}\in\mathcal{D}_{1}}K(D_{i}).$

Now consider a crossing $x=h_{ij}\cap h_{k\ell}$. If $d(x,m_{k\ell})\leqslant
d(x,m_{ij})$ then we assign $x$ to $D_{i}$, and otherwise we assign $x$ to
$D_{k}$. Let $\mathcal{X}(D_{i})$ be the set of crossings assigned to $D_{i}$.
By Observation 1 and the definition of the label
$\\{\lambda_{1}(x),\lambda_{2}(x)\\}$, the disk $D_{i}$ contains at least
$\min\\{\lambda_{1}(x),\lambda_{2}(x)\\}$ crossings
$y\in\pi_{k\ell}[x,m_{k\ell}]$, for any $x=h_{ij}\cap
h_{k\ell}\in\mathcal{X}(D_{i})$. Thus, summing over all crossings
$x\in\mathcal{X}(D_{i})\cap h_{ij}$ and all half-edges $h_{ij}$ incident to
$D_{i}$, we find that

$K(D_{i})\geqslant\frac{1}{2\deg(D_{i})}\sum_{h_{ij}}\sum_{x\in\mathcal{X}(D_{i})\cap
h_{ij}}\min\\{\lambda_{1}(x),\lambda_{2}(x)\\}>\frac{1}{2|\mathcal{D}_{1}|}\sum_{x\in\mathcal{X}(D_{i})}\min\\{\lambda_{1}(x),\lambda_{2}(x)\\},$

where $\deg(D_{i})$ denotes the degree of $D_{i}$ in
$\mathcal{G}^{\times}(\mathcal{D}_{1})$. The factor $\frac{1}{2\deg(D_{i})}$
arises because a crossing $y\in h_{k\ell}$ can be counted up to $2\deg(D_{i})$
times in the expression
$\sum_{x\in\mathcal{X}(D_{i})}\min\\{\lambda_{1}(x),\lambda_{2}(x)\\}$, namely
at most twice for every half-edge incident to $D_{i}$; see Fig. 1(ii). (Twice,
because a pair of paths in a proper path set may cross twice.) Since each
crossing is assigned to exactly one set $\mathcal{X}(D_{i})$, we obtain

$\displaystyle K$
$\displaystyle=\sum_{D_{i}\in\mathcal{D}_{1}}K(D_{i})>\sum_{D_{i}\in\mathcal{D}}\left(\frac{1}{2|\mathcal{D}_{1}|}\sum_{x\in\mathcal{X}(D_{i})}\min\\{\lambda_{1}(x),\lambda_{2}(x)\\}\right)$
$\displaystyle=\frac{1}{2|\mathcal{D}_{1}|}\sum_{x\in\mathcal{X}}\min\\{\lambda_{1}(x),\lambda_{2}(x)\\}.$

$\lhd$

From the Crossing Lemma and our initial assumption that
$|E_{1}|>\sqrt{\frac{4}{c}}\cdot n^{\frac{3+\alpha}{2}}$, we have that

$|\mathcal{X}|\geqslant
c\frac{|E_{1}|^{3}}{n^{2}}>4|E_{1}|n^{1+\alpha}=2|\mathcal{E}_{1}|n^{1+\alpha}.$
(1)

In order to get a rough bound for
$\sum_{x\in\mathcal{X}}\min\\{\lambda_{1}(x),\lambda_{2}(x)\\}$, we will
ignore crossings with small labels, while ensuring that we don’t ignore too
many crossings in total. More precisely, for every half-edge $h_{ij}$, we
disregard its first $n^{1+\alpha}$ crossings, starting from the one closest to
$m_{ij}$. We let $\mathcal{X}^{*}$ denote the set of remaining crossings. Note
that $|\mathcal{X}^{*}|\geqslant|\mathcal{X}|-|\mathcal{E}_{1}|n^{1+\alpha}$,
and $\min\\{\lambda_{1}(x),\lambda_{2}(x)\\}\geqslant n^{1+\alpha}$ for every
$x\in\mathcal{X}^{*}$. Therefore

$K>\frac{1}{2|\mathcal{D}_{1}|}\sum_{x\in\mathcal{X}^{*}}\min\\{\lambda_{1}(x),\lambda_{2}(x)\\}=\frac{1}{2|\mathcal{D}_{1}|}\cdot|\mathcal{X}^{*}|\cdot
n^{1+\alpha}\geqslant\frac{\left(|\mathcal{X}|-|\mathcal{E}_{1}|n^{1+\alpha}\right)n^{1+\alpha}}{2|\mathcal{D}_{1}|}\geqslant\frac{|\mathcal{X}|}{4}n^{\alpha}.$

This means that there exists a crossing $x\in\mathcal{X}$ of ply at least
$\frac{1}{4}n^{\alpha}$, which contradicts the condition of the lemma and thus
finishes the proof.

Step 3: Applying the separator theorem for string graphs. Lee’s separator
theorem for string graphs [18] states that any string graph on $m$ edges
admits a balanced separator of size $O(\sqrt{m})$. It is well known (and easy
to show) that any intersection graph of path-connected sets in the plane is a
string graph. Hence, we can apply Lee’s result to
$\mathcal{G}^{\times}(\mathcal{D}_{1})$ which, as we have just shown, has
$O(n^{\frac{3+\alpha}{2}})$ edges. Thus,
$\mathcal{G}^{\times}(\mathcal{D}_{1})$ has a separator of size
$O(n^{\frac{3+\alpha}{4}})$. If we add the vertices of this separator as
singletons to our clique-based separator $\mathcal{S}$ then, together with the
cliques added in Step 1, we obtain a separator consisting of
$O(n^{\frac{3+\alpha}{4}}+n^{1-\alpha})$ cliques. Picking $\alpha=1/5$, and
anticipating the extension to the case where $\Pi(\mathcal{D}_{1})$ is not a
proper path set, we obtain the following result.

######  Proposition 2.4.

Let $d$ be a well-behaved shortest-path metric on a closed and path-connected
subset $F\subset\Reals^{2}$ and let $\mathcal{D}$ be a set of $n$ geodesic
disks with respect to the metric $d$. Then $\mathcal{G}^{\times}(\mathcal{D})$
has a balanced clique-based separator consisting of $O(n^{4/5})$ cliques.

###  2.2 Bootstrapping

We now describe a bootstrapping mechanism to improve the size of our clique-
based separator. We first explain how to apply the mechanism once, to obtain a
clique-based separator consisting of $O(n^{10/13})$ cliques. Then we apply the
method repeatedly to obtain a separator consisting of $O(n^{3/4+\varepsilon})$
cliques.

#### The basic bootstrapping mechanism.

The idea of our bootstrapping mechanism is as follows. After reducing the ply
in Step 1, we argued that the number of remaining edges is subquadratic. We
can actually reduce the number of edges and crossings even further, by
reducing the maximum degree of the graph
$\mathcal{G}^{\times}(\mathcal{D}_{1})$. To this end, after reducing the ply,
we remove from $\mathcal{G}^{\times}(\mathcal{D}_{1})$ all vertices $D_{i}$
such that $\deg(D_{i})\geqslant n^{\beta}$, for some constant $0<\beta<1$
whose value will be determined later. All these high degree vertices are
placed in our clique-based separator as singletons. If $h$ is the number of
these vertices, then $h\cdot n^{\beta}\leqslant 2|E_{1}|$ and so
$h=O(n^{\frac{3+\alpha}{2}-\beta})$. We denote the resulting graph by
$\mathcal{G}^{\times}(\mathcal{D}_{2})=(\mathcal{D}_{2},E_{2})$ and let
$\mathcal{E}_{2}$ be the half-edges corresponding to the edges in $E_{2}$.

To minimize the number of cliques in our separator, the constants $\alpha$ and
$\beta$ should be chosen to satisfy the equation

$\frac{3+\alpha}{2}-\beta=1-\alpha.$ (2)

Next, we show that after reducing the maximum degree, the number of edges has
also decreased.

######  Lemma 2.5.

For the graph $\mathcal{G}^{\times}(\mathcal{D}_{2})$ defined as above, it
holds that $|E_{2}|\leqslant\sqrt{\frac{4}{c}}n^{1+\frac{\alpha+\beta}{2}}$,
where $c$ is the constant appearing in the Crossing Lemma.

######  Proof 2.6.

The proof is essentially the same as the proof of Lemma 2.2, so we only
mention the key differences. We assume for a contradiction that
$|E_{2}|>\sqrt{\frac{4}{c}}n^{1+\frac{\alpha+\beta}{2}}$. Then, we lower bound
the number of crossings (denoted now by $\mathcal{X}_{2}$) as

$|\mathcal{X}_{2}|\geqslant
c\frac{|E_{2}|^{3}}{n^{2}}>2|\mathcal{E}_{2}|n^{\alpha+\beta}.$

We then proceed with the same labeling procedure as in Step 2 in order to
lower bound the total ply $K_{2}$ of all crossings. A key difference is that
now we only need to divide by $2n^{\beta}$, since $n^{\beta}$ is the maximum
degree of $\mathcal{G}^{\times}(\mathcal{D}_{2})$:

$K_{2}\geqslant\frac{1}{2n^{\beta}}\sum_{x\in\mathcal{X}_{2}}\min\\{\lambda_{1}(x),\lambda_{2}(x)\\}.$

To get an estimate for $K_{2}$, we remove from every half-edge, its first
$n^{\alpha+\beta}$ crossings. In this way there are at least
$|\mathcal{X}_{2}|-|\mathcal{E}_{2}|n^{\alpha+\beta}$ crossings remaining,
each having a minimum label larger than $n^{\alpha+\beta}$. Therefore

$K_{2}>\frac{\left(|\mathcal{X}_{2}|-|\mathcal{E}_{2}|n^{\alpha+\beta}\right)n^{\alpha+\beta}}{2n^{\beta}}>\frac{|\mathcal{X}_{2}|}{4}n^{\alpha}$

so we again get a contradiction, since there has to exist a crossing with ply
at least $\frac{1}{4}n^{\alpha}$.

Step 3 now gives us that $\mathcal{G}^{\times}(\mathcal{D}_{2})$ has a
separator of size $O(n^{\frac{2+\alpha+\beta}{4}})$, whose vertices we add to
our clique-based separator as singletons. In order to minimize the number of
cliques in our separator, we now have the equation

$\frac{2+\alpha+\beta}{4}=1-\alpha.$ (3)

Solving the system of Equations (2) and (3) gives $\alpha=3/13$ and
$\beta=11/13$. This solution corresponds to a clique-based separator of size
$O(n^{10/13})$.

#### Repeated bootstrapping.

The method we just described can be applied repeatedly: After reducing the
maximum degree to $n^{\beta}$, we showed that
$|E_{2}|=O(n^{1+\frac{\alpha+\beta}{2}})$. This allows us to reduce the
maximum degree even more, by placing vertices of degree at least $n^{\gamma}$
in the clique-based separator, for some $\gamma<\beta$. If we repeat this
process $O(\log(1/\varepsilon))$ times, we can obtain a clique-based separator
of size $O(n^{3/4+\varepsilon})$, as is shown in the following theorem.

######  Theorem 2.7.

Let $d$ be a well-behaved shortest-path metric on a closed and path-connected
subset $F\subset\Reals^{2}$, and let $\mathcal{D}$ be a set of $n$ geodesic
disks with respect to the metric $d$. Then $\mathcal{G}^{\times}(\mathcal{D})$
has a balanced clique-based separator consisting of
$O(n^{\frac{3}{4}+\varepsilon})$ cliques.

######  Proof 2.8.

Let $\mathcal{S}$ denote our clique-based separator. As before, we start by
reducing the ply of the subdivision, by finding points of ply at least
$\frac{n^{\alpha_{1}}}{4}$, for some constant $0<\alpha_{1}<1$, and placing
the corresponding cliques into $\mathcal{S}$. Our separator now has a size of
$O(n^{1-\alpha_{1}})$. Let $\mathcal{D}_{1}$ denote the remaining set of disks
and let $\mathcal{G}^{\times}(\mathcal{D}_{1})=(\mathcal{D}_{1},E_{1})$ denote
the resulting subgraph after this step. Next, we repeatedly apply the
following procedure for $i=2,\dotsc,k$: we reduce the maximum degree of
$\mathcal{G}^{\times}(\mathcal{D}_{i-1})$ to $n^{\alpha_{i}}$ (for some
positive constant $\alpha_{i}<\alpha_{i-1}$) by removing from
$\mathcal{G}^{\times}(\mathcal{D}_{i-1})$ vertices of degree at least
$n^{\alpha_{i}}$ and we place them in $\mathcal{S}$ as singletons. We denote
by $\mathcal{D}_{i}$ the remaining set of disks and let
$\mathcal{G}^{\times}(\mathcal{D}_{i})=(\mathcal{D}_{i},E_{i})$ be the
resulting subgraph.

Lemma 2.5 gives us that
$|E_{2}|\leqslant\sqrt{\frac{4}{c}}n^{1+\frac{\alpha_{1}+\alpha_{2}}{2}}$, for
$i=2,\dotsc,k$. In exactly the same way we can show that
$|E_{i}|\leqslant\sqrt{\frac{4}{c}}n^{1+\frac{\alpha_{1}+\alpha_{i}}{2}}$, for
$i=3,...,n$.

During the above procedure, we have introduced $k$ unknown constants
$\alpha_{1},\alpha_{2},\dotsc,\alpha_{k}$ and so we need $k$ equations in
order to calculate their values. To this end, let $h_{i}$ denote the number of
vertices of $G_{i}$ with degree at least $n^{\alpha_{i+1}}$, for
$i=1,\dotsc,{k-1}$. Then, due to Lemma 2.2, we have $h_{1}\cdot
n^{\alpha_{2}}\leqslant 2|E_{1}|,$ and so

$h_{1}=O(n^{\frac{3+\alpha_{1}}{2}-\alpha_{2}}).$

For $i=2,...,k-1$ we have $h_{i}\cdot n^{\alpha_{i+1}}\leqslant 2|E_{i}|,$ and
so

$h_{i}=O(n^{1+\frac{\alpha_{1}+\alpha_{i}}{2}-\alpha_{i+1}}).$

In the last step, we are left with the graph
$\mathcal{G}^{\times}(\mathcal{D}_{k})$, for which we have that
$|E_{k}|\leqslant\sqrt{\frac{4}{c}}n^{1+\frac{\alpha_{1}+\alpha_{k}}{2}}$. We
now apply the separator result on string graphs, which states that any string
graph with $m$ edges has a separator of size $O(\sqrt{m})$. Thus
$\mathcal{G}^{\times}(\mathcal{D}_{k})$ has a separator of size
$O(n^{\frac{2+\alpha_{1}+\alpha_{k}}{4}})$ whose vertices we also place in
$\mathcal{S}$. As a result, the size of our clique-based separator is given by

$|\mathcal{S}|=O\left(n^{1-\alpha_{1}}+\sum_{i=1}^{k-1}h_{k}+n^{\frac{2+\alpha_{1}+\alpha_{k}}{4}}\right)$

which gives the following system of $k$ equations:

$\displaystyle 1-\alpha_{1}$ $\displaystyle=\frac{3+\alpha_{1}}{2}-\alpha_{2}$
(.1) $\displaystyle 1-\alpha_{1}$
$\displaystyle=1+\frac{\alpha_{1}+\alpha_{i}}{2}-\alpha_{{i+1}}\quad\text{for}\quad
i=2,3,...,k-1$ (4.$i$) $\displaystyle 1-\alpha_{1}$
$\displaystyle=\frac{2+\alpha_{1}+\alpha_{k}}{4}$ (4.$k$)

This system can be rewritten as

$\displaystyle 3\alpha_{1}$ $\displaystyle=2\alpha_{2}-1$ (4.1) $\displaystyle
3\alpha_{1}$ $\displaystyle=2\alpha_{i+1}-\alpha_{i}\quad\text{for}\quad
i=2,3,...,k-1$ (4.$i$) $\displaystyle 5\alpha_{1}$
$\displaystyle=2-\alpha_{k}$ (4.$k$)

By multiplying the $i$-th equation above with $2^{i-1}$ and summing up, we can
see that the terms $\alpha_{2},...,\alpha_{k}$ cancel and we are left with the
equation

$\alpha_{1}\left(3\sum_{i=0}^{k-2}2^{i}+5\cdot 2^{k-1}\right)=2^{k}-1,$

which solves to

$\alpha_{1}=\frac{2^{k}-1}{2^{k+2}-3}.$

Thus $1-\alpha_{1}=\frac{3\cdot 2^{k}-2}{4\cdot 2^{k}-3}$ (which converges to
$\frac{3}{4}$ as $k\rightarrow\infty$). By choosing
$k=\log_{2}(1/\varepsilon)$, we have

$1-\alpha_{1}=\frac{3-2\varepsilon}{4-3\varepsilon},$

which is smaller than $\frac{3}{4}+\varepsilon$ for $\varepsilon<1$. (We could
pick $k$ even larger, say $k=\log n$, but the resulting bounds will be only
marginally better and look more ugly.) Therefore, for these choices of
$\alpha_{1}$ and $k$, our clique-based separator has a size of
$O(n^{\frac{3}{4}+\varepsilon})$ as claimed.

De Berg et al. [11] showed that if a class of graphs admits a clique-based
separator consisting of $S(n)$ cliques, and the separator can be constructed
in polynomial time, then one can solve $q$-Coloring in $2^{O(S(n))}$ time.
Note that if we can compute the boundaries $\partial D_{i}$ in polynomial
time,666Typically the time to do this would not only depend on $n$, but also
on the complexity of $F$ and the distance function $d$. For simplicity we
state our results in terms of $n$ only. (This, of course, puts restrictions on
the complexity of $F$ and $d$.) then we can also compute our separator in
polynomial time. Indeed, we can then compute
$\mathcal{G}^{\times}(\mathcal{D})$ and the arrangement of the disk boundaries
in polynomial time, which allows us to do Step 1 (reducing the ply) in
polynomial time. Since a separator for string graphs can be computed in
polynomial time [18], this is easily seen to imply that the separator
construction runs in polynomial time. Thus we obtain the following result.

######  Corollary 2.9.

Let $d$ be a shortest-path metric on a connected subset $F\subset\Reals^{2}$
and let $\mathcal{D}$ be a set of $n$ geodesic disks with respect to the
metric $d$, where $d$ is such that the boundaries $\partial D_{i}$ of the
disks in $\mathcal{D}$ can be computed in polynomial time. Let $q\geqslant 1$
and $\varepsilon>0$ be fixed constants. Then $q$-Coloring can be solved in
$2^{O(n^{\frac{3}{4}+\varepsilon})}$ time on
$\mathcal{G}^{\times}(\mathcal{D})$.

###  2.3 Obtaining a proper path system

So far we assumed that $\Pi(\mathcal{D})$ is a proper path set. In general
this may not be the case, since the paths in $\Pi(\mathcal{D})$ may overlap
along 1-dimensional subpaths and a pair of paths can meet multiple times. (The
latter can happen since shortest paths need not be unique). Lemma 2.10 will
allow us to still work with a proper path set in our proof. The proof of this
lemma requires two technical assumptions on our shortest-path metric $d$. We
thus now introduce the concept of a _well-behaved shortest-path metric_.

#### Well-behaved shortest-path metrics.

We assume that for any finite set $P=\\{p_{1},\ldots,p_{n}\\}$ of points in
$F$, there exists a set $\Pi(P)=\\{\pi_{ij}:1\leqslant i<j\leqslant n\\}$ of
shortest paths between the points in $P$ with the following properties:

  1. 1.

For any two paths $\pi_{ij},\pi_{k\ell}\in\Pi(P)$, the intersection
$\pi_{ij}\cap\pi_{k\ell}$ consists of finitely many connected components.

  2. 2.

Let $P^{+}\supset P$ be the set of endpoints of these components, and let
$\Gamma_{ij}$ be the set of subpaths into which $\pi_{ij}$ is partitioned by
the points in $P^{+}$. Note that any two subpaths $\gamma\in\Gamma_{ij}$ and
$\gamma^{\prime}\in\Gamma_{k\ell}$ either have disjoint interiors or they are
identical. Let $\Gamma=\bigcup_{i,j}\Gamma_{ij}$ be the set of all distinct
subpaths. Then there are values $\delta_{1},\delta_{2}>0$ such that the
following holds.

     * •

For any $v\in P^{+}$, the Euclidean ball $B(v,\delta_{1})$ of radius
$\delta_{1}$ centered at $v$ only intersects paths from $\Pi(P)$ that contain
$v$, and inside $B(v,\delta_{1})$ any two paths are either disjoint (except at
$v$) or they coincide. Moreover, the balls $B(v,\delta_{1})$ for $v\in P^{+}$
are pairwise disjoint.

     * •

Outside the balls $B(v,\delta_{1})$, the minimum distance between any two
subpaths $\gamma,\gamma^{\prime}\in\Gamma$ is at least $\delta_{2}$.

We call a metric satisfying these conditions _well-behaved_. The conditions
are easily seen to be satisfied when $F$ is a closed and connected polygonal
region and the paths $\pi_{ij}$ are shortest (in the Euclidean sense) paths
inside $F$. In fact, $F$ does not have to be polygonal; its boundary may
consist of finitely many constant-degree algebraic curves. Another example is
when the paths in $\pi_{ij}$ are projections onto $\Reals^{2}$ of shortest
paths on a polyhedral terrain, or when the paths are shortest paths in a
weighted polygonal subdivision. (In the latter case, the length of a section
of the path inside a region is multiplied by the weight of the region [21]. In
this setting, shortest paths are piece-wise linear and so they satisfy the
conditions.)

We can now proceed with the proof of the lemma. It might be known, but we have
not been able to find a reference. Recall that $E$ is the edge set of
$\mathcal{G}^{\times}(\mathcal{D})$.

######  Lemma 2.10.

Let $d$ be a well-behaved shortest-path metric on a closed and path-connected
subset $F\subset\Reals^{2}$, and let
$\Pi(\mathcal{D})=\\{\pi_{ij}:(D_{i},D_{j})\in E\\}$ be a set of shortest
paths with the properties stated above. Then there is a proper path set
$\Pi^{\prime}(\mathcal{D})=\\{\pi^{\prime}_{ij}:(D_{i},D_{j})\in E\\}$ in
$\Reals^{2}$ with the following property: for every pair
$\pi^{\prime}_{ij},\pi^{\prime}_{k\ell}$ of crossing paths in
$\Pi^{\prime}(\mathcal{D})$, the corresponding paths $\pi_{ij},\pi_{k\ell}$ in
$\Pi(\mathcal{D})$ intersect.

######  Proof 2.11.

We will prove the lemma in two steps. First, we modify the paths such that any
two paths $\pi_{ij}$ and $\pi_{k\ell}$ meet in a single connected component,
and then we perturb these paths slightly to obtain a set
$\Pi^{\prime}(\mathcal{D})$ where any two paths cross in at most two points.

The first modification is done as follows. For each pair
$\pi_{ij},\pi_{k\ell}\in\Pi(\mathcal{D})$, and for each connected component
$I\subset\pi_{ij}\cap\pi_{k\ell}$, we add both endpoints of $I$ to the set
$P$, thus (by the first property of well-behaved shortest-path metrics)
obtaining a finite set $P^{+}$. The set $P^{+}$, together with the pieces of
the paths $\pi_{ij}$ connecting them, forms a plane graph
$\mathcal{G}^{+}=(P^{+},E^{+})$. We now slightly modify the edge lengths in
$\mathcal{G}^{+}$, to ensure that there is a unique shortest path between any
two points in $P^{+}$, and we replace each original path $\pi_{ij}$ by the
shortest path between $p_{i}$ and $p_{j}$ in $\mathcal{G}^{+}$; see Fig. 2(i)
for an example.

Figure 2: (i) The input paths (left) and the graph $\mathcal{G}^{+}$ after re-
routing the paths (right). (ii) The thickened graph. (iii) Drawing the paths
inside a thick vertex.

Since the shortest paths between any two vertices in $\mathcal{G}^{+}$ are
unique, two paths $\pi_{ij},\pi_{k\ell}$ do not intersect in more than one
connected component. Moreover, the new paths are still shortest paths under
the original metric. Formally, the perturbation of the edges lengths is done
as follows. Let $e_{1},e_{2},...,e_{k}$ be any ordering on the edges of
$\mathcal{G}^{+}$. Then, perturb the edge lengths such that the new lengths
are given by $|e_{i}^{\prime}|=|e_{i}|+2^{i}\varepsilon$, for an arbitrarily
small $\varepsilon>0$. Any path that was shortest initially, will remain
shortest and no two paths have the same length.

Next we show how to slightly perturb the paths such that all crossings are
proper. For that, we will make use of the second property of well-behaved
shortest-path metrics to thicken the graph $\mathcal{G}^{+}$. Intuitively, we
replace the edges of $\mathcal{G}^{+}$ by thick curves and its vertices by
small balls. Within each thick curve, we can slightly separate all paths that
use the corresponding edge. Curves going to the same vertex meet at the disk
around it. We then show that it’s possible to route paths within these balls,
such that paths only possibly cross within the balls where they meet for the
first time or for the last time. Formally this is done as follows.

Let $\delta_{1},\delta_{2}>0$ be the values specified in the second property
of well-behaved metrics. We thicken $\mathcal{G}^{+}$ by replacing each vertex
$v\in P^{+}$ by the ball $B(v,\delta_{1})$—we call this ball a _thick vertex_
—and by replacing each edge in $\mathcal{G}^{+}$ by a _thick edge_ of width
$2\delta_{2}/3$. (Formally, we take the Minkowski sum of the original edge and
a ball of radius $\delta/3$, and remove the parts of the resulting thick edge
inside the balls $B(v,\delta_{1})$.) See Fig. 2(ii) for an example. Note that
the thick edges are pairwise disjoint.

Now we draw the paths $\pi_{ij}\in\Pi^{\prime}(\mathcal{D})$ one by one, as
follows. We start at the point $p_{i}$ and follow the thick edges of
$\pi_{ij}$ until we reach $p_{ij}$. An invariant of our process is that the
paths may only cross inside thick vertices, and not inside thick edges. It is
easy to see that this invariant can be maintained: when $\pi_{ij}$ enters a
thick edge in between two previously drawn paths, then we can stay in between
these two paths until we reach the next thick vertex. It will be convenient to
view the edges as roads with two lanes, where we will always stay in the right
lane as we draw the paths. (Thus the lanes that we use depend on whether we
draw $\pi_{ij}$ from $p_{i}$ to $p_{j}$ or in the other direction; this choice
can be made arbitrarily.)

Routing inside a thick vertex $B(v,\delta_{1})$ is done as follows. Let
$\deg(v)$ denote the degree of vertex $v$ in $\mathcal{G}^{+}$. We view
$B(v,\delta_{1})$ as a roundabout with $\deg(v)-1$ lanes
$L_{1},\ldots,L_{\deg(v)-1}$, where $L_{1}$ is the outermost lane. Now suppose
we draw a path $\pi_{ij}$ and we enter the roundabout through some thick edge.
Then draw $\pi_{ij}$ as follows: if $\pi_{ij}$ leaves the roundabout at the
$j$-th exit in counterclockwise order (counting from the road on which we
enter) then we will use lane $L_{j}$ on the roundabout to draw $\pi_{ij}$; see
Figure 2(iii) for some examples. We can easily do this in such a way that we
maintain the following invariant: paths entering and exiting the roundabout on
the same roads do not cross. Note that paths that use the same two edges
incident to $v$ but that were drawn in the opposite direction, do not cross
either. Thus two paths $\pi_{ij},\pi_{k\ell}$ may only cross when $v$ is
either the first or the last vertex of $\pi_{ij}\cap\pi_{k\ell}$, and when
this happens they have a single crossing inside $B(v,\delta_{1})$. Hence, two
paths have at most two crossings and these crossings are proper crossing.

There is one thing that we have swept under the rug so far, namely what
happens at the start vertex (or end vertex) of the path $\pi_{ij}$. In this
case we simply draw $\pi_{ij}$ from $p_{i}$ to the correct exit road (or we
draw $\pi_{ij}$ from the entry road to $p_{j}$). This way we may have to
create intersection with paths $\pi_{kl}$ traversing the roundabout, but this
is okay since this is then the first (or last) vertex where $\pi_{ij}$ meets
$\pi_{kl}$.

Recall that the assumption that $\Pi(\mathcal{D})$ is a proper path set was
used so that we could apply the Crossing Lemma. Now, instead of applying the
Crossing Lemma to (a subset of) $\Pi(\mathcal{D})$ we apply it to (the
corresponding subset of) $\Pi^{\prime}(\mathcal{D})$. Then we obtain a bound
on $|\mathcal{X}|$, the number of crossings of the perturbed paths, which by
Lemma 2.10 gives us a collection of points on the intersections of the
original paths. These points can be used as the set $\mathcal{X}$ in the proof
of Lemma 2.2. Note that Observation 1 in that proof still holds. Also note
that the fact that crossings may now coincide is not a problem: we just need
to re-define $\lambda_{1}(x)$ (and, similarly, $\lambda_{2}(x)$) so that
crossings that coincide with $x$ are also counted. We conclude that the proof
also works without the assumption that $\Pi(\mathcal{D})$ is a proper path
set.

##  3 Application to distance oracles

With our clique-based separator at hand, we can apply standard techniques to
obtain an almost-exact hop-distance oracle for
$\mathcal{G}^{\times}(\mathcal{D})$. This is done using a _separator tree_ $T$
as follows.

  * •

Let $\mathcal{S}$ be a clique-based separator for
$\mathcal{G}^{\times}(\mathcal{D})$. The root of the separator tree $T$
stores, for each disk $D_{i}\in\mathcal{D}$ and each clique
$C_{k}\in\mathcal{S}$, the value $\mathit{hdist}(D_{i},C_{k})=\min_{D_{j}\in
C_{k}}\mathit{hdist}(D_{i},D_{j})$, where $\mathit{hdist}(D_{i},D_{j})$
denotes the hop-distance between $D_{i}$ and $D_{j}$ in
$\mathcal{G}^{\times}(\mathcal{D})$. Thus we need $O(n\cdot
n^{3/4+\varepsilon})=O(n^{7/4+\varepsilon})$ storage at the root.

  * •

Let $\mathcal{D}_{A}$ and $\mathcal{D}_{B}$ be the two subsets into which
$\mathcal{S}$ splits $\mathcal{D}\setminus\mathcal{S}$, such that
$|\mathcal{D}_{A}|,|\mathcal{D}_{B}|\leqslant 2n/3$ and there are no edges
between $\mathcal{D}_{A}$ and $\mathcal{D}_{B}$. We recursively construct
separator trees $T_{A}$ for $\mathcal{D}_{A}$ and $T_{B}$ for
$\mathcal{D}_{B}$, which become the two subtrees of the root of $T$.

The amount of storage of the structure satisfies the recurrence
$S(n)=O(n^{7/4+\varepsilon})+S(n_{A})+S(n_{B})$, where $n_{A},n_{B}\leqslant
2n/3$ and $n_{A}+n_{B}\leqslant n$. This solves to
$S(n)=O(n^{7/4+\varepsilon})$.

To answer a query for the hop-distance between two disks $D_{i},D_{j}$ we
proceed as follows. First, we determine
$Z_{1}\coloneq\min_{C_{k}\in\mathcal{S}}\left(\mathit{hdist}(D_{i},C_{k})+\mathit{hdist}(C_{k},D_{j})\right)$.
When $D_{i}$ and $D_{j}$ do not lie in the same part of the partition, we are
done and report $Z_{1}$. Otherwise, assuming without loss of generality that
$D_{i},D_{j}\in\mathcal{D}_{A}$, we recursively query in $T_{A}$, thus
obtaining a value $Z_{2}$, and we report $\min(Z_{1},Z_{2})$. Thus the query
time satisfies the recurrence $Q(n)=O(n^{3/4+\varepsilon})+Q(n_{A})$, where
$n_{A}\leqslant 2n/3$, which solves to $Q(n)=O(n^{3/4+\varepsilon})$. It is
easily seen that our query reports a value $d^{*}$ such that
$d^{*}\leqslant\mathit{hdist}(D_{i},D_{j})\leqslant d^{*}+1$.

######  Theorem 3.1.

Let $d$ be a well-behaved shortest-path metric on a closed and path-connected
subset $F\subset\Reals^{2}$, and let $\mathcal{D}$ be a set of $n$ geodesic
disks with respect to the metric $d$. Let $\varepsilon>0$ be any fixed
constant. Then there is a distance oracle for
$\mathcal{G}^{\times}(\mathcal{D})$ that uses $O(n^{\frac{7}{4}+\varepsilon})$
storage and that can report, for any two query disks
$D_{i},D_{j}\in\mathcal{D}$, in $O(n^{3/4+\varepsilon})$ time a value $d^{*}$
such that $d^{*}\leqslant\mathit{hdist}(D_{i},D_{j})\leqslant d^{*}+1$.

##  4 Concluding remarks

In this paper, we showed that the intersection graph of a set of geodesic
disks, in any well-behaved shortest-path metric in the plane, admits a clique-
based separators of sublinear size, using a method that is quite different
from previously used approaches. Separators have been used extensively to
obtain efficient graph algorithms, and clique-based separators have already
found many uses as well. We gave two straightforward applications of our new
clique-based separators, namely for $q$-Coloring and almost exact distance
oracles, but we expect our separator to have more applications. More
generally, we hope that our paper inspires more research on intersection
graphs of geodesic disks in the general setting that we studied—or, more
modestly, of geodesic disks in polygons with holes or on terrains.

An obvious open problem is to improve upon our bounds: do intersection graphs
of geodesic disks admit a separator of size $o(n^{3/4})$, either in general or
perhaps in the setting of polygons with holes? Our distance oracle is the
first almost exact distance oracle with sublinear query time and subquadratic
storage in such a general setting, but (besides our novel separator) it uses
only standard techniques. It would be interesting to see if more advanced
techniques can be applied to get better bounds.

## References

  * [1] Ittai Abraham and Cyril Gavoille.  On approximate distance labels and routing schemes with affine stretch.  In Proc. $25^{th}$ International Symposium on Distributed Computing (DISC 2011), volume 6950 of Lecture Notes in Computer Science (ARCoSS), pages 404–415, 2011.  https://doi.org/10.1007/978-3-642-24100-0_39 doi:10.1007/978-3-642-24100-0_39.
  * [2] M. Ajtai, V. Chvátal, M.M. Newborn, and E. Szemerédi.  Crossing-free subgraphs.  In Peter L. Hammer, Alexander Rosa, Gert Sabidussi, and Jean Turgeon, editors, Theory and Practice of Combinatorics, volume 60 of North-Holland Mathematics Studies, pages 9–12. North-Holland, 1982.  https://doi.org/doi.org/10.1016/S0304-0208(08)73484-4 doi:doi.org/10.1016/S0304-0208(08)73484-4.
  * [3] Srinivasa Rao Arikati, Danny Z. Chen, L. Paul Chew, Gautam Das, Michiel H. M. Smid, and Christos D. Zaroliagis.  Planar spanners and approximate shortest path queries among obstacles in the plane.  In Proc. 4th Annual European Symposium on Algorithms (ESA 1996), volume 1136 of Lecture Notes in Computer Science, pages 514–528, 1996.  https://doi.org/10.1007/3-540-61680-2_79 doi:10.1007/3-540-61680-2_79.
  * [4] Boris Aronov, Mark de Berg, and Leonidas Theocharous.  A clique-based separator for intersection graphs of geodesic disks in $\Reals^{2}$.  In Proc. 40th International Symposium on Computational Geometry (SoCG 2024), LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
  * [5] Édouard Bonnet and Pawel Rzazewski.  Optimality program in segment and string graphs.  Algorithmica, 81(7):3047–3073, 2019.  https://doi.org/10.1007/s00453-019-00568-7 doi:10.1007/s00453-019-00568-7.
  * [6] Timothy M. Chan and Dimitrios Skrepetos.  Approximate Shortest Paths and Distance Oracles in Weighted Unit-Disk Graphs.  In Proc. 34th International Symposium on Computational Geometry (SoCG 2018), volume 99, pages 24:1–24:13, 2018.  https://doi.org/10.4230/LIPIcs.SoCG.2018.24 doi:10.4230/LIPIcs.SoCG.2018.24.
  * [7] Panagiotis Charalampopoulos, Pawel Gawrychowski, Yaowei Long, Shay Mozes, Seth Pettie, Oren Weimann, and Christian Wulff-Nilsen.  Almost optimal exact distance oracles for planar graphs.  J. ACM, 70(2):12:1–12:50, 2023.  https://doi.org/10.1145/3580474 doi:10.1145/3580474.
  * [8] Shiri Chechik.  Approximate distance oracles with constant query time.  In Proc. 46th Symposium on Theory of Computing (STOC 2014), pages 654–663, 2014.  https://doi.org/10.1145/2591796.2591801 doi:10.1145/2591796.2591801.
  * [9] Mark de Berg.  A note on reachability and distance oracles for transmission graphs.  Computing in Geometry and Topology, 2(1):4:1–4:15, 2023.  https://doi.org/doi.org/10.57717/cgt.v2i1.25 doi:doi.org/10.57717/cgt.v2i1.25.
  * [10] Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, and Tom C. van der Zanden.  A framework for Exponential-Time-Hypothesis-tight algorithms and lower bounds in geometric intersection graphs.  SIAM J. Comput., 49:1291–1331, 2020.  https://doi.org/10.1137/20M1320870 doi:10.1137/20M1320870.
  * [11] Mark de Berg, Sándor Kisfaludi-Bak, Morteza Monemizadeh, and Leonidas Theocharous.  Clique-based separators for geometric intersection graphs.  Algorithmica, 85(6):1652–1678, 2023.  https://doi.org/10.1007/S00453-022-01041-8 doi:10.1007/S00453-022-01041-8.
  * [12] Hristo Djidjev and Shankar M. Venkatesan.  Reduced constants for simple cycle graph separation.  Acta Informatica, 34(3):231–243, 1997.  https://doi.org/10.1007/s002360050082 doi:10.1007/s002360050082.
  * [13] Jacob Fox and János Pach.  Separator theorems and Turán-type results for planar intersection graphs.  Advances in Mathematics, 219(3):1070–1080, 2008.  https://doi.org/doi.org/10.1016/j.aim.2008.06.002 doi:doi.org/10.1016/j.aim.2008.06.002.
  * [14] Bin Fu.  Theory and application of width bounded geometric separators.  Journal of Computer and System Sciences, 77(2):379–392, 2011.  https://doi.org/10.1016/j.jcss.2010.05.003 doi:10.1016/j.jcss.2010.05.003.
  * [15] Jie Gao and Li Zhang.  Well-separated pair decomposition for the unit-disk graph metric and its applications.  SIAM Journal on Computing, 35(1):151–169, 2005.  https://doi.org/10.1137/S0097539703436357 doi:10.1137/S0097539703436357.
  * [16] Sariel Har-Peled and Kent Quanrud.  Approximation algorithms for polynomial-expansion and low-density graphs.  SIAM J. Comput., 46(6):1712–1744, 2017.  https://doi.org/10.1137/16M1079336 doi:10.1137/16M1079336.
  * [17] Hung Le and Christian Wulff-Nilsen.  Optimal approximate distance oracle for planar graphs.  In Proc. 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS 2021), pages 363–374. IEEE, 2021.  https://doi.org/10.1109/FOCS52979.2021.00044 doi:10.1109/FOCS52979.2021.00044.
  * [18] James R. Lee.  Separators in region intersection graphs.  In Proc. 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67 of LIPIcs, pages 1:1–1:8, 2017.  https://doi.org/10.4230/LIPIcs.ITCS.2017.1 doi:10.4230/LIPIcs.ITCS.2017.1.
  * [19] Thomas Leighton.  Complexity Issues in VLSI.  Foundations of Computing Series. MIT Press, 2003.
  * [20] Richard J. Lipton and Robert Endre Tarjan.  A separator theorem for planar graphs.  SIAM J. Appl. Math, 36(2):177–189, 1977.  https://doi.org/doi/10.1137/0136016 doi:doi/10.1137/0136016.
  * [21] Joseph S. B. Mitchell and Christos H. Papadimitriou.  The weighted region problem: Finding shortest paths through a weighted planar subdivision.  J. ACM, 38(1):18–73, jan 1991.  https://doi.org/10.1145/102782.102784 doi:10.1145/102782.102784.
  * [22] Mihai Patrascu and Liam Roditty.  Distance oracles beyond the Thorup-Zwick bound.  In Proc. 51st Annual Symposium on Foundations of Computer Science (FOCS 2010), pages 815–823, 2010.  https://doi.org/10.1109/FOCS.2010.83 doi:10.1109/FOCS.2010.83.
  * [23] Christian Sommer.  Shortest-path queries in static networks.  ACM Comput. Surv., 46(4):45:1–45:31, 2014.  https://doi.org/10.1145/2530531 doi:10.1145/2530531.
  * [24] Mikkel Thorup and Uri Zwick.  Approximate distance oracles.  J. ACM, 52(1):1–24, 2005.  https://doi.org/10.1145/1044731.1044732 doi:10.1145/1044731.1044732.
  * [25] William Thurston.  The Geometry and Topology of 3-Manifolds.  Princeton Lecture Notes, 1978–1981.