# Computing Feasible Trajectories for an Articulated Probe in Three
Dimensions111A preliminary version of this work was presented at the 31st
Annual Canadian Conference on Computational Geometry.

Ovidiu Daescu<EMAIL_ADDRESS>Ka Yaw Teo<EMAIL_ADDRESS>Department of Computer Science, University of Texas at Dallas, Richardson, TX,
USA.

###### Abstract

Consider an input consisting of a set of $n$ disjoint triangular obstacles in
$\mathbb{R}^{3}$ and a target point $t$ in the free space, all enclosed by a
large sphere $S$ of radius $R$ centered at $t$. An articulated probe is
modeled as two line segments $ab$ and $bc$ connected at point $b$. The length
of $ab$ can be equal to or greater than $R$, while $bc$ is of a given length
$r\leq R$. The probe is initially located outside $S$, assuming an
_unarticulated_ configuration, in which $ab$ and $bc$ are collinear and $b\in
ac$. The goal is to find a feasible (obstacle-avoiding) probe trajectory to
reach $t$, with the condition that the probe is constrained by the following
sequence of moves – a straight-line insertion of the unarticulated probe into
$S$, possibly followed by a rotation of $bc$ at $b$ for at most $\pi/2$
radians, so that $c$ coincides with $t$.

We prove that if there exists a feasible probe trajectory, then a set of
_extremal_ feasible trajectories must be present. Through careful case
analysis, we show that these extremal trajectories can be represented by
$O(n^{4})$ combinatorial events. We present a solution approach that
enumerates and verifies these combinatorial events for feasibility in overall
$O(n^{4+\epsilon})$ time using $O(n^{4+\epsilon})$ space, for any constant
$\epsilon>0$. The enumeration algorithm is highly parallel, considering that
each combinatorial event can be generated and verified for feasibility
independently of the others. In the process of deriving our solution, we
design the first data structure for addressing a special instance of circular
sector emptiness queries among polyhedral obstacles in three dimensional
space, and provide a simplified data structure for the corresponding emptiness
query problem in two dimensions.

††journal: JoCG

##  1 Introduction

In this paper, we address the three-dimensional (3D) version of the
_articulated probe trajectory planning problem_ introduced by Teo, Daescu, and
Fox [20]. We are given a 3D workspace containing a set $P$ of $n$ interior
disjoint triangular obstacles and a target point $t$ in the free space, all
located within a large sphere $S$ of radius $R$ centered at $t$ (see Figure
1). An articulated probe is modeled as two line segments $ab$ and $bc$ joined
at point $b$. Line segment $ab$ has a length of $R$ or greater, while $bc$ has
a fixed length $r\in(0,R]$. Line segment $bc$ may rotate around $b$.

Figure 1: Articulated probe trajectory in 3D. After inserting line segment
$abc$ into sphere $S$, in order to reach target point $t$, line segment $bc$
may be required to rotate from its intermediate position (dashed line segment)
to its final position (solid line segment).

The probe is said to have an _unarticulated_ configuration if line segments
$ab$ and $bc$ are collinear, and $b\in ac$. Otherwise, the probe has an
_articulated_ configuration – that is, $bc$ has been rotated around $b$, and
$bc$ is no longer collinear with $ab$.

The probe begins its trajectory in an unarticulated configuration outside
sphere $S$. The unarticulated probe, represented by straight line segment
$abc$, is at first inserted along a straight line into $S$. After completing
the insertion, line segment $bc$ may be rotated around point $b$ up to $\pi/2$
radians in order to reach the target point $t$. Hence, the final configuration
of the probe could be either unarticulated or articulated. The _intermediate_
configuration of the probe is the unarticulated configuration after the
insertion and before the rotation. Without loss of generality, point $a$ is
assumed to be located on $S$ after the insertion.

A _feasible_ probe trajectory consists of an initial insertion of straight
line segment $abc$ into sphere $S$, possibly followed by a rotation of line
segment $bc$ around point $b$, such that point $c$ ends at the target point
$t$, while avoiding the obstacles in the process of insertion and rotation.
The objective of the problem is to find a feasible probe trajectory, if one
exists.

As illustrated in Figure 1, a feasible probe trajectory is planar – that is,
its motion always lies in a plane $\Pi$ passing through the target point $t$.
Since line segment $bc$ may only rotate as far as $\pi/2$ radians around point
$b$, for any feasible probe trajectory, point $b$ is the first (and only)
intersection between line segment $ab$ and the sphere $C$ of radius $r$
centered at the target point $t$. When line segment $bc$ rotates around point
$b$, the area swept by $bc$ is a sector $\sigma$ of a circle $D$ in plane
$\Pi$ (i.e., a portion of a disk enclosed by two radii and a circular arc),
where $D$ is of radius $r$ and centered at a point on sphere $C$. Circular
sector $\sigma$ always has an endpoint of one of its bounding radii located at
the target point $t$.

### Motivation

Besides its pointed relevance to robotics, the outlined problem arises
particularly from planning for minimally invasive surgeries. In fact, surgical
instruments that can be modeled by our simple articulated probe are already in
clinical use (e.g., da Vinci EndoWrist by Intuitive Surgical), given their
enhanced capability in reaching remote targets while circumventing surrounding
critical structures [19]. In our problem setting, a human body cavity can be
viewed as (a subset of) workspace $S$, and any critical organ/tissue can be
represented by using a triangle mesh. Despite its importance and relevance,
the problem has never been investigated in three dimensions from a theoretical
viewpoint, and only a handful of results in two dimensions have been reported
[8, 20].

### Related work

The motion of a linkage or kinematic chain – that is, an assembly of rigid
links and joints – has been investigated in many different aspects, including
the basic geometric properties and topology of linkages (e.g., reconfiguration
and locked decision) [4, 7] as well as application-driven questions related to
linkage design and motion planning [6, 13].

Approximation methods based on sampling [11, 14] and subdivision [5, 9, 22]
are commonly used (and widely regarded as efficient) for motion planning
involving complex multi-link robots with high degrees-of-freedom. However, a
robotic linkage can often be associated with spatial (link or joint)
constraints, resulting in a restricted free configuration space, which has
proven to be challenging for inexact sampling-based algorithms to find valid
solutions [21]. In addition, sampling- and subdivision-based approaches are
only complete within their inherent limits – that is, probabilistically and
resolution-wise, respectively.

In contrast to previous work on polygonal linkages, which are generally
allowed to rotate unrestrictedly at their joints while moving from a start to
a final configuration [6, 7, 13], our study is concerned with a simple
articulated two-bar linkage subjected to a specific sequence of moves –
namely, a straight-line insertion of the linkage followed by a rotation at its
joint. Moreover, one of the links is assumed to have a length $\geq R$ (i.e.,
radius of spherical workspace $S$). Without resorting to approximation, we
develop an exact geometric-combinatorial approach to solve the proposed path
planning problem.

Teo, Daescu, and Fox [20] originally proposed the aforementioned trajectory
planning problem in two dimensions (2D), and they presented an $O(n^{2}\log
n)$-time, $O(n\log n)$-space algorithm for finding a feasible trajectory
amidst $n$ line segment obstacles. The algorithm was based on computing
extremal trajectories that are tangent to one or two obstacle vertices. In
addition, they showed that, for any constant $\delta>0$, a feasible trajectory
of a clearance $\delta$ from the obstacles can be determined in $O(n^{2}\log
n)$ time using $O(n^{2})$ space. These algorithmic approaches were also
extended to the case of $h$ polygonal obstacles, where a feasible trajectory
can be found in $O(n^{2}+h^{2}\log n)$ time using $O(n\log n)$ space when no
clearance is required, or $O(n^{2})$ space otherwise.

Daescu and Teo [8] later addressed a variant of the trajectory planning
problem where the length $r$ of the end segment $bc$ is not fixed. They
demonstrated that, for any constant $\epsilon>0$, the shortest length $r>0$
for which a feasible trajectory exists can be determined in
$O(n^{2+\epsilon})$ time using $O(n^{2+\epsilon})$ space, and at least one
such trajectory can be reported with the same time/space complexity. The
proposed algorithm can be extended to reporting all feasible values of $r$ in
$O(n^{5/2})$ time using $O(n^{2+\epsilon})$ space. In the same work, Daescu
and Teo also showed that, for a given $r$, the feasible solution space for the
trajectory planning problem can be characterized by a simple-curve arrangement
of complexity $O(k)$, and the arrangement can be constructed in $O(n\log n+k)$
time using $O(n+k)$ space, where $k=O(n^{2})$ is the number of vertices of the
arrangement.

### Results and contributions

In this paper, we describe an algorithm that computes a feasible probe
trajectory in 3D, if one exists, in $O(n^{4+\epsilon})$ time using
$O(n^{4+\epsilon})$ space, for any constant $\epsilon>0$. First, we prove that
if there exists a feasible probe trajectory, then some _extremal_ feasible
trajectories must be present. An extremal trajectory is characterized by its
intersections or tangencies with a combination of obstacle edges, vertices,
and/or surfaces. Through careful case analysis, we show that these extremal
trajectories can be represented by $O(n^{4})$ combinatorial events. Our
algorithm is based on enumerating and verifying these combinatorial events for
feasibility. As an alternative, an $O(n^{5})$-time algorithm with $O(n)$-space
usage is achievable by performing a simple $O(n)$-check on each of the
$O(n^{4})$ events.

The main new difficulty that arises in this study, when compared to the 2D
case in [20], is the possibility that for an extremal trajectory in 3D, a
segment of the probe may intersect an obstacle edge at an interior point, and
an obstacle endpoint may be incident to the interior of the circular sector
representing the area swept by the end segment $bc$ of the probe. As a
consequence, in order to address the 3D case, procedures and data structures
different from those previously used in [20] are required, particularly for
extremal trajectory computation and circular sector emptiness queries.

While deriving our solution approach, we develop the first data structure for
solving a special case of the circular sector emptiness query problem in 3D,
where the query circular sector has a fixed radius $r$ and an endpoint of its
arc located at fixed point $t$. We present a data structure of size
$O(n^{4+\epsilon})$ for answering a query of the sort in $O(\log n)$ time.
When mapped to the plane, this result yields a new data structure for solving
the corresponding circular sector emptiness query problem in 2D. Our new
$\mathbb{R}^{2}$ query data structure simplifies the two-part approach
formerly proposed in [20] while maintaining the same time and space
complexity. Sharir and Shaul [18] proposed a solution based on semialgebraic
range searching for circular cap (i.e., portion of a circle cut off by a line
and larger than a semidisk) emptiness queries in 2D. These circular sector
emptiness queries, in 2D and 3D, are considered to be of independent interest.
To the best of the authors’ knowledge, there has been no published data
structure for general circular sector emptiness queries in 3D or even 2D.

The remainder of the paper is organized as follows. In Section 2, we prove the
presence of extremal feasible probe trajectories. In Section 3, we describe an
algorithm for computing extremal probe trajectories and verifying them for
feasibility. We conclude in Section 4 by providing a summary of our results
and a few related open questions.

##  2 Extremal feasible trajectories

In this section, we prove that if there exists a feasible probe trajectory,
then a set of extremal feasible trajectories must also be present. We begin by
defining a series of terminologies used in our ensuing discussion.

Let $\ell$ denote a line segment of the probe. In addition, let $\sigma$ and
$\gamma$ denote a circular sector (i.e., area swept by $bc$, as previously
described) and its arc, respectively. Let $\tau$ be a triangular obstacle of
$P$ in $\mathbb{R}^{3}$, and let $e$ denote en edge of $\tau$. Without loss of
generality, assume that $\tau$ is not co-planar with $t$, and $\ell$ is not
parallel to $e$. Line segment $\ell$ may intersect $e$ at an endpoint of $e$,
an interior point of $e$, or none.

######  Definition 2.1 (Support vertex of $\ell$).

If $\ell$ intersects $e$ at an endpoint $p$ of $e$, then $p$ is called a
_support vertex_ of $\ell$.

######  Definition 2.2 (Support edge of $\ell$).

If $\ell$ intersects $e$ at an interior point of $e$, then $e$ is called a
_support edge_ of $\ell$.

Thus, a _support_ of $\ell$ can be either a support vertex or a support edge.
Suppose, without loss of generality, that $\sigma$ and $e$ lie in different
planes.

######  Definition 2.3 (Support vertex of $\sigma$).

If $\sigma$ contains an endpoint $p$ of $e$, then $p$ is a _support vertex_ of
$\sigma$.

######  Definition 2.4 (Support edge of $\gamma$).

If $\gamma$ is tangent to $e$ at an interior point of $e$, then $e$ is a
_support edge_ of $\gamma$.

######  Definition 2.5 (Support surface of $\gamma$).

If $\gamma$ is tangent to the surface of $\tau$, then the surface is a
_support surface_ of $\gamma$.

For an illustration of the various types of supports just described, see
Figure 2.

Figure 2: Support vertex, edge, and surface. An endpoint of edge $e_{1}$ is a
support vertex of line segment $\ell$. Edge $e_{2}$ is a support edge of
$\ell$. An endpoint of $e_{3}$ is a support vertex of circular sector
$\sigma$. Edge $e_{4}$ supports circular arc $\gamma$ at an interior point of
$e_{4}$. Triangle $\tau$ is a support surface of $\gamma$.

A line segment is _extremal_ (or _isolated_) with respect to a set of support
vertices and edges if the line segment cannot be moved continuously while
maintaining its intersections with these vertices and edges. Analogously, a
probe trajectory is isolated by a set of supports if the trajectory cannot be
altered without losing any of its supports. Note that the term “isolated” has
the same meaning as “extremal,” and they will be used interchangeably
hereafter.

######  Lemma 2.1.

Assume that a feasible unarticulated trajectory exists – that is, the
unarticulated probe can be inserted into $S$ to reach $t$ while avoiding the
obstacles (i.e., $t$ can see to infinity without obstruction). Then, there
exists an extremal feasible unarticulated trajectory such that the probe is
isolated by either one support vertex or two support edges.

###### Proof.

Let $T$ be a feasible probe trajectory such that its final configuration is
unarticulated. Specifically, in the final configuration of the probe, $abc$ is
a straight line segment, and point $c$ coincides with $t$.

Let $\Pi$ be an arbitrary plane passing through $t$ and containing line
segment $abc$. Assume that plane $\Pi$ intersects at least one triangular
obstacle. Observe that such an arbitrary plane $\Pi$ always exists; otherwise,
workspace $S$ must be free of obstacles. Let $T^{\prime}$ be the trajectory
resulting from rotating $T$ around $t$ in plane $\Pi$ until $T$ intersects an
obstacle edge at either i) an endpoint or ii) an interior point.

If the intersection occurs at an endpoint $v$ of the obstacle edge, then we
have a feasible trajectory $T^{\prime}$ that is isolated by a support vertex
$v$ (for $t$ and $v$ define a unique line).

On the other hand, suppose that $T^{\prime}$ intersects the obstacle edge at
an interior point. Let $e_{1}$ denote the intersecting obstacle edge, and
$\Psi$ be the unique plane containing $e_{1}$ and $t$. When $T^{\prime}$ is
rotated around $t$ in plane $\Psi$ until $T^{\prime}$ intersects an endpoint
of $e_{1}$ or some obstacle edge $e_{2}$, a new feasible trajectory
$T^{\prime\prime}$ is obtained. If $T^{\prime\prime}$ intersects $e_{1}$ or
$e_{2}$ at an endpoint, then $T^{\prime\prime}$ is isolated with respect to a
support vertex. If $T^{\prime\prime}$ intersects $e_{2}$ at an interior point,
then $T^{\prime\prime}$ is isolated with respect to two support edges (i.e.,
$e_{1}$ and $e_{2}$). ∎

######  Lemma 2.2.

Assume that a feasible articulated trajectory exists – that is, the
unarticulated probe can be inserted into $S$, and a subsequent rotation of
$bc$ around $b$ can be performed to reach $t$, all while avoiding the
obstacles. Then, there exists either

  1. i)

an extremal feasible unarticulated trajectory or

  2. ii)

an extremal feasible trajectory such that the probe assumes an articulated
final configuration, and the trajectory is isolated with respect to at most
four supports (edges, vertices, surfaces, or a combination of the three).

###### Proof.

Let $T$ denote a feasible probe trajectory such that its final configuration
is articulated. Namely, in the final configuration of the probe, $ab$ and $bc$
are not collinear, and point $c$ coincides with $t$.

Let $\Pi$ be the unique plane containing $ab$ and $t$. Since the trajectory of
the probe is planar (i.e., in plane $\Pi$), without loss of generality, assume
that $bc$ of $T$ is rotated clockwise around $b$ to reach $t$ in plane $\Pi$.
For ease of subsequent discussion, $bc$ and $bt$ (of an articulated
trajectory) would be used to indicate line segment $bc$ of the probe in its
intermediate and final configurations, respectively.

A feasible trajectory $T^{\prime}$ can be obtained by rotating $ab$ of $T$
around $b$ in clockwise direction in plane $\Pi$ until either $ab$ and $bt$
become collinear or $ab$ intersects an obstacle edge $e_{1}$ outside $C$. In
the former case, $T^{\prime}$ has an unarticulated final configuration, and by
directly applying Lemma 2.1, we obtain an extremal feasible unarticulated
trajectory as a result. In the latter case, let $T^{\prime\prime}$ be the
trajectory resulting from rotating $bt$ of $T^{\prime}$ around $t$ counter-
clockwise in plane $\Pi$, while keeping $ab$ intersecting $e_{1}$, until
either 1) $bt$ or 2) $ab$ intersects some obstacle edge $e_{2}$. Trajectory
$T^{\prime\prime}$ is feasible, and the proof is given in [20].

##### Case 1: $bt$ intersects $e_{2}$ (inside $C$)

Let $p_{1}$ be the intersection point between $ab$ and $e_{1}$. Let
${e_{2}}^{\prime}$ be the projection of $e_{2}$ onto the surface of sphere $C$
from center $t$. Notice that ${e_{2}}^{\prime}$ is a circular arc on $C$, and
point $b$ of trajectory $T^{\prime\prime}$ must lie on ${e_{2}}^{\prime}$ as
long as $bt$ intersects $e_{2}$ (see Figure 3).

Figure 3: Illustration for Case 1.

Let $\sigma_{bct}$ denote the minor circular sector (with a central angle
$\leq\pi/2$ radians) bounded by radii $bc$ and $bt$, and let $\gamma_{ct}$ be
the circular arc of $\sigma_{bct}$. Let point $b$ of $T^{\prime\prime}$ be
translated along ${e_{2}}^{\prime}$ in the direction such that the obtuse
angle $\angle abt$ increases, while keeping $ab$ intersecting $e_{1}$ at
$p_{1}$, until a) $bt$, b) $bc$, c) $ab$, d) $\sigma_{bct}$, or e)
$\gamma_{ct}$ intersects with an obstacle edge $e_{3}$, f) $\gamma_{ct}$ is
tangent to the surface of some obstacle triangle, g) $bt$ intersects with an
endpoint of $e_{2}$, or h) $ab$ becomes collinear with $bt$. Let
$T^{\prime\prime\prime}$ denote the resulting trajectory, as depicted in
Figure 3. Since $T^{\prime\prime\prime}$ is obtained by simply perturbing
$T^{\prime\prime}$ until the trajectory comes into contact with an obstacle
(or $\angle abt$ reaches $\pi$ radians), $T^{\prime\prime\prime}$ is feasible.

##### Case 1(a): $bt$ intersects $e_{3}$

Note that two generic line segments and a point induce an incident line in 3D
space. Since $t$ is fixed and $bt$ intersects two obstacle edges $e_{2}$ and
$e_{3}$, $bt$ is isolated (and thus point $b$ is fixed).

Let $\Psi$ be the unique plane containing $e_{1}$ and $b$. As illustrated in
Figure 4 Case 1(a), let $T^{\prime\prime\prime\prime}$ be the trajectory
obtained from rotating $abc$ of $T^{\prime\prime\prime}$ around $b$ in plane
$\Psi$ in the direction such that the obtuse angle $\angle abt$ increases
until i) $bc$, ii) $ab$, iii) $\sigma_{bct}$, or iv) $\gamma_{ct}$ intersects
with some obstacle edge $e_{4}$, v) $\gamma_{ct}$ is tangent to the surface of
an obstacle triangle, vi) $ab$ intersects an endpoint of $e_{1}$, or vii) $ab$
becomes collinear with $bt$. Obviously, given that
$T^{\prime\prime\prime\prime}$ is derived from $T^{\prime\prime\prime}$
through a straightforward perturbation, $T^{\prime\prime\prime\prime}$ is
feasible.

Figure 4: Illustrations for Cases 1(a)–(d).

##### Case 1(a)(i), (ii): $bc$ or $ab$ intersects $e_{4}$

Since $abc$ intersects two obstacle edges $e_{1}$ and $e_{4}$ (and $b$ is
fixed), $abc$ is isolated. Thus, $T^{\prime\prime\prime\prime}$ is an extremal
feasible articulated trajectory.

##### Case 1(a)(iii): $\sigma_{bct}$ intersects $e_{4}$ (at one of its
endpoints)

In 3D space, the intersection of two generic planes is a line. Since the plane
containing $\sigma_{bct}$ and the plane $\Psi$ containing $e_{1}$ and $b$ are
fixed, their intersection line, which supports $abc$, is fixed. Hence,
$T^{\prime\prime\prime\prime}$ is an isolated feasible articulated trajectory.

##### Case 1(a)(iv), (v): $\gamma_{ct}$ intersects $e_{4}$ or is tangent to
the surface of an obstacle triangle

The plane containing $\sigma_{bct}$ is isolated, and so is $abc$ (for more
insight, see Cases 1(e) and (f) below). As a result,
$T^{\prime\prime\prime\prime}$ is an isolated feasible articulated trajectory.

##### Case 1(a)(vi): $ab$ intersects an endpoint of $e_{1}$

Since $b$ is fixed, $abc$ is isolated with respect to $b$ and the intersected
endpoint of $e_{1}$. Thus, $T^{\prime\prime\prime\prime}$ is an extremal
feasible articulated trajectory.

##### Case 1(a)(vii): $ab$ becomes collinear with $bt$

In this case, by directly applying Lemma 2.1, we claim that
$T^{\prime\prime\prime\prime}$ is an extremal feasible unarticulated
trajectory.

##### Case 1(b): $bc$ intersects $e_{3}$

Note that $ab$ intersects $e_{1}$, and $bc$ intersects $e_{3}$. Let
$P(e_{1},e_{3})$ be the set of points $q$ for which there exists a line
segment starting at $e_{1}$, passing through $q$, and ending at $e_{3}$. Let
$I$ be the intersection of $P(e_{1},e_{3})$, $C$, and ${e_{2}}^{\prime}$ (for
an illustration, see Figure 4 Case 1(b), where $I$ is indicated as the portion
of the blue dashed line lying in the green shaded area). Notice that $I$ is a
circular arc on $C$. An isolated feasible trajectory can be obtained by
translating point $b$ of $T^{\prime\prime\prime}$ along $I$ in the direction
such that the obtuse angle $\angle abt$ increases until i) $bt$, $bc$, $ab$,
$\sigma_{bct}$, or $\gamma_{ct}$ intersects with some obstacle edge $e_{4}$,
ii) $\gamma_{ct}$ is tangent to the surface of an obstacle triangle, iii)
$bt$, $bc$, or $ab$ reaches an endpoint of its currently intersecting obstacle
edge, or iv) $ab$ becomes collinear with $bt$. The detailed analyses for Cases
1(b)(i)–(iv) (as well as similar others in the cases that follow) are omitted
herein due to their similarity to those in Case 1(a).

##### Case 1(c): $ab$ intersects $e_{3}$

Notice that $ab$ intersects two edges $e_{1}$ and $e_{3}$. Assume, without
loss of generality, that $e_{1}$ and $e_{3}$ are intersected by $ab$ in the
way depicted in Figure 4 Case 1(c). Let $P(e_{1},e_{3})$ be the set of points
$q$ for which there exists a ray starting at $e_{1}$, passing through $e_{3}$,
and then through $q$. Let $I$ be the intersection of $P(e_{1},e_{3})$, $C$,
and ${e_{2}}^{\prime}$. Note that $I$ is a circular arc on $C$. Circular arc
$I$ is illustrated, in Figure 4 Case 1(c), as the portion of the blue dashed
line lying in the green shaded area. An isolated feasible trajectory can be
obtained by moving point $b$ of $T^{\prime\prime\prime}$ along $I$ in the
direction that increases the obtuse angle $\angle abt$ until i) $bt$, $bc$,
$ab$, $\sigma_{bct}$, or $\gamma_{ct}$ intersects with an obstacle edge
$e_{4}$, ii) $\gamma_{ct}$ is tangent to the surface of an obstacle triangle,
iii) $bt$ or $ab$ reaches an endpoint of its currently intersecting obstacle
edge, or iv) $ab$ becomes collinear with $bt$.

##### Case 1(d): $\sigma_{bct}$ intersects $e_{3}$ (at one of its endpoints)

Observe, as shown in Figure 4 Case 1(d), that $T^{\prime\prime\prime}$ can be
made isolated if point $b$ of $T^{\prime\prime\prime}$ is further translated
along ${e_{2}}^{\prime}$, while keeping $ab$ intersecting $e_{1}$ and
maintaining the incidence between $\sigma_{bct}$ and $e_{3}$, until i) $bt$,
$bc$, $ab$, $\sigma_{bct}$, or $\gamma_{ct}$ intersects with some obstacle
edge $e_{4}$, ii) $\gamma_{ct}$ is tangent to the surface of an obstacle
triangle, iii) $bt$ or $ab$ reaches an endpoint of its currently intersecting
obstacle edge, or iv) $ab$ becomes collinear with $bt$. The resulting
trajectory is feasible.

##### Case 1(e): $\gamma_{ct}$ intersects $e_{3}$

Let $D$ be a sphere of radius $r$ with center $b$ located on sphere $C$. Note
that $D$ passes through $t$. Consider the scenario that $D$ is tangent to
obstacle edge $e_{3}$. When $D$ is rotated around $t$ while maintaining its
tangency to $e_{3}$, the center $b$ of $D$ translates along a curve
${e_{3}}^{\prime}$ on $C$ (see Figure 5).

Figure 5: Illustration for Case 1(e). A top sectional view along the plane
containing $e_{3}$ and $t$.

A plane can be defined by using two points on $D$ and the center $b$ of $D$.
Consider a sphere $D$ with center $b$ on ${e_{3}}^{\prime}$. Sphere $D$
intersects $t$ and is tangent to $e_{3}$ at a point $p$. Thus, we can define a
plane $\Pi_{b}$ containing $t$, $p$, and $b$, for any given point $b$ on
${e_{3}}^{\prime}$.

Notice that $\gamma_{ct}$ is a circular arc on $D$ originating at $t$, and
$\gamma_{ct}$ must be on the circle of intersection between $D$ and $\Pi_{b}$,
for some point $b$ on ${e_{3}}^{\prime}$. Since ${e_{2}}^{\prime}$ and
${e_{3}}^{\prime}$ intersect at a point (i.e., point $b$ on $C$), point $b$ is
fixed. As a result, plane $\Pi_{b}$ is set, and so is the circle on which
$\gamma_{ct}$ lies. If $\Pi_{b}$ does not contain $e_{1}$, then $abc$ is
isolated. Otherwise, $abc$ can be rotated around $b$, while continuing to
intersect $e_{1}$, until either $ab$ or $bc$ intersects an obstacle edge (or
an endpoint of $e_{1}$). In the end of either scenario, an extremal feasible
trajectory is obtained.

##### Case 1(f): $\gamma_{ct}$ is tangent to the surface of an obstacle
triangle

The analysis is similar to Case 1(e). Let $\tau$ denote the obstacle triangle
to whose surface $\gamma_{ct}$ is tangent. As $D$ is rotated around $t$ while
remaining tangent to the surface of $\tau$, the center $b$ of $D$ moves along
a curve $\kappa_{\tau}$ on $C$. Given that ${e_{2}}^{\prime}$ and
$\kappa_{\tau}$ intersect at a point, $b$ is fixed. The same argument as in
Case 1(e) immediately follows.

##### Case 1(g): $bt$ intersects an endpoint of $e_{2}$

Given that $t$ is fixed, $bt$ of $T^{\prime\prime\prime}$ is isolated by its
intersection with an endpoint of $e_{2}$. A similar analysis as in Case 1(a)
then follows.

##### Case 1(h): $bc$ becomes collinear with $bt$

In this case, Lemma 2.1 is directly applicable, resulting in an extremal
feasible unarticulated trajectory.

##### Case 2: $ab$ intersects $e_{2}$ (outside $C$)

Using similar arguments as given in Case 1, we can obtain an isolated feasible
articulated trajectory such that i) $ab$ intersects two edges, and ii) any of
$bt$, $bc$, $ab$, $\sigma_{bct}$, and $\gamma_{ct}$ are supported by at most
two vertices, edges, and/or surfaces.

One may find some overlaps between Cases 1 and 2. On the whole, an extremal
feasible articulated trajectory is characterized by its intersections (or
tangencies) with at most four supports consisting of obstacle endpoints,
edges, surfaces, or a combination of the three. This concludes the proof of
Lemma 2.2. ∎

##  3 Finding and validating extremal trajectories

Based on Lemmas 2.1 and 2.2, we can compute the set of extremal probe
trajectories and verify them for feasibility. The algorithms and data
structures required are discussed in this section.

###  3.1 Extremal feasible unarticulated trajectories

Let $V$ and $E$ denote the set of vertices and edges of the triangles of $P$,
respectively. We compute the set $R$ of rays, each of which i) originates at
point $t$, ii) is either passing through a vertex of $V$ or isolated with
respect to two support edges of $E$, and iii) does not intersect any triangle
of $P$ in its interior. Each ray of $R$ represents an extremal feasible
unarticulated trajectory. Set $R$ can be obtained by computing the visibility
polyhedron from point $t$ in $O(n^{2})$ time using $O(n^{2})$ space [15]. In
fact, this approach yields all feasible unarticulated solutions, since the
visibility polyhedron gives all unbounded rays from $t$ to infinity (i.e.,
feasible unarticulated trajectories).

######  Lemma 3.3.

The set of all feasible unarticulated probe trajectories can be found in
$O(n^{2})$ time using $O(n^{2})$ space.

###  3.2 Extremal feasible articulated trajectories

We begin by computing the set of extremal articulated trajectories, which are
characterized by $O(n^{4})$ combinatorial events (see Lemma 2.2). As detailed
next, these extremal articulated trajectories can be enumerated in $O(n^{4})$
time either geometrically or algebraically.

####  3.2.1 Computing extremal articulated trajectories

Table LABEL:tab1 lists all the distinct cases of isolated articulated
trajectories, each of which is indicated by the number of obstacle edges
(i.e., support edges) intersected by line segments $ab$, $bc$, $bt$, and
circular arc $\gamma_{ct}$, and the number of obstacle endpoints (i.e.,
support vertices) incident on the interior of circular sector $\sigma_{bct}$.
Table LABEL:tab1 also provides, for each case, a brief description of the
method (i.e., a sequence of geometric operations) and the worst-case time
complexity for finding an extremal articulated trajectory. When describing the
geometric operations in each case, obstacles edges are divided into those
lying inside and outside $C$. Given that an obstacle edge may intersect $C$ at
most twice, an obstacle edge may be partitioned into at most three line
segments.

Table 1: Extremal articulated trajectories. Case | $ab$ | $bc$ | $bt$ | $\sigma_{bct}$ | $\gamma_{ct}$ |  Method | Time
---|---|---|---|---|---|---|---
1* | 1 | 1 | 1 | 1 |  |  See main text in Section 3.2.1. | $n^{4}$
2 | 1 | 2 | 1 |  |  |  – For any three obstacle edges $e_{1}$, $e_{2}$, and $e_{3}$ (one outside $C$, and two inside or outside $C$), compute the projection (curve $\kappa_{1}$) of the hyperboloid that contains $e_{1}$, $e_{2}$, and $e_{3}$ on $C$. – For every obstacle edge $e_{4}$ inside $C$, compute its projection (curve $\kappa_{2}$) on $C$. – Compute the intersection of $\kappa_{1}$ and $\kappa_{2}$. | $n^{4}$
3 | 1 | 1 | 2 |  |  |  – For any two obstacle edges $e_{1}$ and $e_{2}$ (one inside $C$, and the other inside or outside $C$), compute the projection (area $A$) of $P(e_{1},e_{2})$ on $C$. – For any two obstacle edges $e_{3}$ and $e_{4}$ inside $C$, compute the radial line segment $s$ originating at $t$ and intersecting $e_{3}$ and $e_{4}$, and determine the intersection point $b$ between $s$ and $C$. – Note that a distinct $abc$ is given by a point $b$ lying on $A$. | $n^{4}$
4 | 1 |  | 1 | 2 |  |  – For any two obstacle endpoints $v_{1}$ and $v_{2}$ (within distance $2r$ from $t$), compute the plane $\Pi$ that contains $v_{1}$, $v_{2}$, and $t$. – For any obstacle edge $e_{1}$ outside $C$, compute the intersection of $e_{1}$ and $\Pi$. – For any obstacle edge $e_{2}$ inside $C$, compute the intersection of $e_{2}$ and $\Pi$. | $n^{4}$
5 | 1 |  | 2 | 1 |  |  – For any two obstacle edges $e_{1}$ and $e_{2}$ inside $C$, compute the radial line segment $s$ originating at $t$ and intersecting $e_{1}$ and $e_{2}$, and determine the intersection point $b$ between $s$ and $C$. – For any obstacle endpoint $v$ (within distance $2r$ from $t$), compute the plane $\Pi$ that contains $v$, $b$, and $t$. – For any obstacle edge $e_{3}$ outside $C$, compute the intersection of $e_{3}$ and $\Pi$. | $n^{4}$
6* | 2 |  | 1 | 1 |  |  See main text in Section 3.2.1. | $n^{4}$
7* | 2 | 1 |  | 1 |  |  See main text in Section 3.2.1. | $n^{4}$
8 | 2 | 1 | 1 |  |  |  – For any three obstacle edges $e_{1}$, $e_{2}$, and $e_{3}$ (two outside $C$, and one inside or outside $C$), compute the projection (curve $\kappa_{1}$) of the hyperboloid that contains $e_{1}$, $e_{2}$, and $e_{3}$ on $C$. – For any obstacle edge $e_{4}$ inside $C$, compute its projection (curve $\kappa_{2}$) on $C$. – Compute the intersection of $\kappa_{1}$ and $\kappa_{2}$. | $n^{4}$
9 | 2 | 2 |  |  |  |  For any four obstacle edges (two outside $C$, and two inside or outside $C$), compute the incidence lines induced by the four obstacle edges. | $n^{4}$
10 | 2 |  | 2 |  |  |  – For any two obstacle edges $e_{1}$ and $e_{2}$ outside $C$, compute the projection (area $A$) of $P(e_{1},e_{2})$ on $C$. – For any two obstacle edges $e_{3}$ and $e_{4}$ inside $C$, compute the radial line segment $s$ originating at $t$ and intersecting $e_{3}$ and $e_{4}$, and determine the intersection point $b$ between $s$ and $C$. – Note that a distinct $abc$ is given by a point $b$ lying on $A$. | $n^{4}$
11 | 2 |  |  | 2 |  |  – For any two obstacle endpoints $v_{1}$ and $v_{2}$ (within distance $2r$ from $t$), compute the plane $\Pi$ that contains $v_{1}$, $v_{2}$, and $t$. – For any two obstacle edges $e_{1}$ and $e_{2}$ outside $C$, compute their intersections with $\Pi$. | $n^{4}$
12 | 3 | 1 |  |  |  |  For any four obstacle edges (three outside $C$, and one inside or outside $C$), compute the incidence lines induced by the four obstacle edges. | $n^{4}$
13 | 3 |  | 1 |  |  |  – For any three obstacle edges $e_{1}$, $e_{2}$, and $e_{3}$ outside $C$, compute the projection (curve $\kappa_{1}$) of the hyperboloid that contains $e_{1}$, $e_{2}$, and $e_{3}$ on $C$. – For any obstacle edge $e_{4}$ inside $C$, compute its projection (curve $\kappa_{2}$) on $C$. – Compute the intersection of $\kappa_{1}$ and $\kappa_{2}$. | $n^{4}$
14* | 3 |  |  | 1 |  |  See main text in Section 3.2.1. | $n^{4}$
15 | 4 |  |  |  |  |  For any four obstacle edges outside $C$, compute the incidence lines induced by the four obstacle edges. | $n^{4}$
16 | 1 |  | 1 |  | 1 |  – For any obstacle edge $e_{1}$ (within distance $2r$ from $t$), compute the curve $\kappa_{1}$ on which point $b$ (i.e., the center of the sphere $D$ tangent to $e_{1}$) lies. – For any obstacle edge $e_{2}$ inside $C$, compute its projection (curve $\kappa_{2}$) on $C$. – Compute the intersection point $b$ between $\kappa_{1}$ and $\kappa_{2}$. – Compute the plane $\Pi$ that contains $t$, $b$, and the point of intersection/tangency between $e_{1}$ and $D$. – For any obstacle edge $e_{3}$ outside $C$, compute the intersection of $\Pi$ and $e_{3}$. – Assume that $\Pi$ is not the same as the plane that contains $b$ and $e_{3}$. | $n^{3}$
17 | 1 | 1 | 1 |  | 1 |  – This is similar to Case 16 above with a different assumption at the end. – Assume that $\Pi$ is the same as the plane that contains $b$ and $e_{3}$. – For any obstacle edge $e_{4}$ inside or outside $C$, compute the intersection of $\Pi$ and $e_{4}$. | $n^{4}$
18 | 1 |  | 1 | 1 | 1 |  This can be thought of as Case 16 with an additional obstacle vertex supporting $\sigma_{bct}$ (which does not contribute to additional extremal trajectories). | $n^{3}$
19 | 1 |  | 2 |  | 1 |  This can be thought of as Case 16 with an additional obstacle edge intersecting $bt$ (which does not contribute to additional extremal trajectories). | $n^{3}$
20 | 2 | 1 |  |  | 1 |  – For any three obstacle edges $e_{1}$, $e_{2}$, and $e_{3}$ (two outside $C$ and one inside or outside $C$), compute the projection (curve $\kappa_{1}$) of the hyperboloid that contains $e_{1}$, $e_{2}$, and $e_{3}$ on $C$. – For any obstacle edge $e_{4}$ (within distance $2r$ from $t$), compute the curve $\kappa_{2}$ on which point $b$ (i.e., the center of the sphere $D$ tangent to $e_{4}$) lies. – Compute the intersection point $b$ between $\kappa_{1}$ and $\kappa_{2}$. | $n^{4}$
21 | 2 |  | 1 |  | 1 |  – This is similar to Case 16 with a different assumption at the end. – Assume that $\Pi$ is the same as the plane that contains $b$ and $e_{3}$. – For any obstacle edge $e_{4}$ outside $C$, compute the intersection of $\Pi$ and $e_{4}$. | $n^{4}$
22* | 2 |  |  | 1 | 1 |  See main text in Section 3.2.1. | $n^{4}$

For conciseness, certain scenarios are omitted from Table LABEL:tab1 given
their trivial nature, and they include those involving the isolation of a
feasible articulated trajectory due to incidence of its line segment (i.e.,
$ab$, $bc$, or $bt$) with obstacle endpoints (i.e., support vertices). In
addition, the cases in which $\gamma_{ct}$ is tangent to the surface of an
obstacle triangle are omitted due to their similarity to those where
$\gamma_{ct}$ is tangent to an obstacle edge.

Note that the set of extremal articulated trajectories, in all cases besides
those denoted by * in Table LABEL:tab1, can be found by using a sequence of
simple geometric operations (e.g., computing the intersection of two line
segments or planes). An extremal articulated trajectory in each of the five
cases designated by * can be computed by using an algebraic-geometric
approach. Given that these five cases are characteristically similar, as a
demonstration, let us take a closer look at Case 1 from an algebraic point of
view.

Recall that, in Case 1, $ab$ intersects an edge $e_{1}$, $bt$ intersects an
edge $e_{2}$, and $bc$ intersects an edge $e_{3}$. In addition, $\sigma_{bct}$
intersects an obstacle endpoint $v$. Let $p$ (resp. $q$) denote the
intersection between $ab$ and $e_{1}$ (resp. $bt$ and $e_{2}$).

Edges $e_{1}$, $e_{2}$, and $e_{3}$ can be expressed in parametric form as
follows:

$\displaystyle
e_{1}=\\{(1-\lambda_{1})u_{1}+\lambda_{1}v_{1}:\lambda_{1}\in\mathbb{R},0\leq\lambda_{1}\leq
1\\}$ $\displaystyle
e_{2}=\\{(1-\lambda_{2})u_{2}+\lambda_{1}v_{2}:\lambda_{2}\in\mathbb{R},0\leq\lambda_{2}\leq
1\\}$ $\displaystyle
e_{3}=\\{(1-\lambda_{3})u_{3}+\lambda_{1}v_{3}:\lambda_{3}\in\mathbb{R},0\leq\lambda_{3}\leq
1\\}$

where $u_{i},v_{i}\in\mathbb{R}^{3}$ are the two endpoints of edge $e_{i}$ for
$i=1,2,3$. Analogously, line segments $bt$ and $pq$ can be defined,
respectively, as

$\displaystyle
bt=\\{(1-\lambda_{bt})b+\lambda_{bt}t:\lambda_{bt}\in\mathbb{R},0\leq\lambda_{bt}\leq
1\\}$ $\displaystyle
pq=\\{(1-\lambda_{pq})p+\lambda_{pq}q:\lambda_{pq}\in\mathbb{R},0\leq\lambda_{pq}\leq
1\\}$

where $b,p,q,t\in\mathbb{R}^{3}$. Since $bt$ intersects $e_{3}$,

$(1-\lambda_{bt})b+\lambda_{bt}t=(1-\lambda_{3})u_{3}+\lambda_{1}v_{3}$ (1)

Furthermore, given that $b$ must lie on a sphere of fixed radius $r$ centered
at $t$,

$(b-t)\cdot(b-t)=r^{2}$ (2)

where $\cdot$ designates the dot product. Note that $b$ must also be located
on $pq$. Thus,

$b=(1-\lambda_{pq})p+\lambda_{pq}q$ (3)

Since $p$ and $q$ are points on $e_{1}$ and $e_{2}$, respectively,

$\displaystyle p=(1-\lambda_{1})u_{1}+\lambda_{1}v_{1}$ (4) $\displaystyle
q=(1-\lambda_{2})u_{2}+\lambda_{1}v_{2}$ (5)

The normal vector $n$ of the plane $\Pi$ defined by points $t$, $b$, and $v$
can be expressed as

$n=(b-t)\times(v-t)$

where $\times$ denotes the cross product. Since $p$ (and thus $q$) must be in
plane $\Pi$,

$\begin{split}n\cdot(p-t)&=0\\\
\big{[}(b-t)\times(v-t)\big{]}\cdot(p-t)&=0\end{split}$ (6)

At last, without loss of generality, $t$ is assumed to be located at the
origin:

$t=(0,0,0)$ (7)

Note that Equations 1, 3, 4, 5, and 7 are in vector form, and each of these
equations yields three scalar equations (i.e., $x$, $y$, and $z$ components).
For instance, Equation 1 can be expressed, in scalar form, as

$\displaystyle(1-\lambda_{bt})b_{x}+\lambda_{bt}t_{x}=(1-\lambda_{3})u_{3x}+\lambda_{1}v_{3x}$
$\displaystyle(1-\lambda_{bt})b_{y}+\lambda_{bt}t_{y}=(1-\lambda_{3})u_{3y}+\lambda_{1}v_{3y}$
$\displaystyle(1-\lambda_{bt})b_{z}+\lambda_{bt}t_{z}=(1-\lambda_{3})u_{3z}+\lambda_{1}v_{3z}$

Similarly, each of the vector variables $b$, $t$, $p$, and $q$ consists of
three scalar components (e.g., $b=(b_{x},b_{y},b_{z})$). Hence, we have, in
total, a system of 17 (scalar) parametric equations with 17 unknown (scalar)
variables, which can be solved in constant time.

All in all, the worst-case running time for computing an extremal articulated
trajectory is $O(n^{4})$.

####  3.2.2 Validating extremal articulated trajectories

An extremal articulated trajectory is deemed feasible if and only if i) line
segment $ab$ and ii) circular sector $\sigma$ do not intersect with any
triangular obstacle in its interior. Checking for these scenarios can be
reduced to the following two query problems – i) ray shooting query and ii)
circular sector emptiness query.

#### Ray shooting queries

A ray shooting query among $n$ interior disjoint triangles can be performed to
determine whether a query line segment $ab$ intersects with any triangular
obstacle in its interior (i.e., whether a query line segment stabs through the
interior of an obstacle triangle). According to de Berg et al. [3] and
Pellegrini [16], such a query can be answered in $O(\log n)$ time using
$O(n^{4+\epsilon})$ preprocessing time and space, for any constant
$\epsilon>0$. Alternatively, by using the data structure proposed by Agarwal
and Matousek [2], which provides a trade-off between space and time, a ray
shooting query (amidst $n$ triangles) can be answered in
$O(n^{1+\epsilon}/m^{1/4})$ time using $O(m)$ storage and $O(m^{1+\epsilon})$
preprocessing time, for any $n\leq m\leq n^{4}$. By employing this fairly
complex data structure, given that we have $O(n^{4})$ queries, when $m=n$, we
obtain $O(n^{3/4+\epsilon})$ time per query and $O(n^{19/4+\epsilon})$ total
time.

#### Circular sector emptiness queries

In this section, we address a special instance of the circular sector
emptiness query problem in 3D.

Given a set $P$ of $n$ triangles in $\mathbb{R}^{3}$, preprocess it so that,
for a query circular sector $\sigma$ with a fixed radius $r$ and an endpoint
of its arc located at fixed point $t$, one can quickly determine whether
$\sigma$ intersects $P$.

Let $\Pi$ be a plane passing through point $t$. We can parameterize $\Pi$ by
using two variables $(I,\Omega)$ (see Figure 6, where $\Pi_{0}$ is the plane
with $I=0$ and $\Omega=0$).

Figure 6: Characterization of $\rho_{s}$ as function of $\theta$ in $\Pi$.

Let ${C_{\Pi}}^{\prime}$ be the circle in $\Pi$ with radius $\sqrt{2}r$ and
the center at $t$. Let $\tau$ be a triangle that intersects $\Pi$ in a line
segment $s$. Observe that a query circular sector $\sigma$ in $\Pi$, as
described above, can only intersect with $\tau$ if $s$ intersects the interior
of ${C_{\Pi}}^{\prime}$.

Let $C_{\Pi}$ denote the circle of radius $r$ centered at $t$ in $\Pi$. For
any point $b\in C_{\Pi}$, let $\theta\in[0,2\pi)$ be the angle of $tb$
relative to the $x$-axis of $\Pi$ (labeled as the $x^{\prime}$-axis in Figure
6). Let $bc^{\prime}$ denote the farthest radius from $bt$, with respect to
the circle of radius $r$ centered at $b$ in $\Pi$, before the minor circular
sector bounded by radii $bt$ and $bc^{\prime}$ intersects with $s$. Let
$\rho_{s}$ be the angle of $bc^{\prime}$ with respect to $bt$. Recall that
line segment $bc$ of the probe, after the insertion of the probe has
completed, may only rotate up to $\pi/2$ radians in either direction in plane
$\Pi$. Thus, $\rho_{s}\in[0,\pi/2]$. Here we consider $\rho_{s}$ to be the
clockwise angle from $bt$ in plane $\Pi$. The other case can be handled
symmetrically.

We fix plane $\Pi$ (i.e., $I$ and $\Omega$) and proceed to characterize
$\rho_{s}$ as a function of $\theta$. Two different cases are examined
separately, depending on whether line segment $s$ lies 1) inside $C_{\Pi}$ or
2) outside $C_{\Pi}$ and inside ${C_{\Pi}}^{\prime}$. Note that a line segment
$s$ may intersect $C_{\Pi}$ or ${C_{\Pi}}^{\prime}$ (or both). Since a line
segment may intersect a circle at most two times, such a line segment can be
partitioned into at most three line segments – one inside and two outside the
circle – before proceeding with the following analysis.

##### Case 1: $s$ lies inside $C_{\Pi}$

For brevity, the quarter-circular sector associated with a point $b$ (i.e.,
the maximum possible area swept by $bc$ to reach $t$), where the angle of $tb$
relative to the $x^{\prime}$-axis is $\theta$, is henceforth referred to as
the _quart-sector of $\theta$_.

Let $\phi_{s,1}$, $\phi_{s,2}$, and $\phi_{s,3}$ be defined as follows (see
Figure 7A). Angle $\phi_{s,1}$ is the smallest angle $\theta$ at which the
circular arc of the quart-sector of $\theta$ intersects with $s$ at one of its
endpoints or an interior point. Angle $\phi_{s,2}$ is the smallest angle
$\theta$ at which the radius $bt$ of the quart-sector of $\theta$ intersects
with $s$ at one of its endpoints. Angle $\phi_{s,3}$ is the largest angle
$\theta$ at which the radius $bt$ of the quart-sector of $\theta$ intersects
with $s$ at one of its endpoints. In other words, as $\theta$ varies from 0 to
$2\pi$, $\phi_{s,1}$ and $\phi_{s,3}$ are the angles $\theta$ at which the
quart-sector of $\theta$ first and last intersects with $s$, respectively.

Figure 7: (A) Characterizing $\rho_{s}(\theta)$ for
$\theta\in[\phi_{s,1},\phi_{s,2}]$ in Case 1. Illustrations for
$\rho_{s}(\theta)$ when (B) $\phi_{s,1}<\theta<\alpha_{s}$, (C)
$\theta=\alpha_{s}$, and (D) $\alpha_{s}<\theta<\phi_{s,2}$, respectively.

For a line segment $s$ lying inside $C_{\Pi}$, as shown in Figure 7, we are
only concerned with computing $\rho_{s}$ for
$\theta\in[\phi_{s,1},\phi_{s,2}]$, given that
$\theta\in[\phi_{s,2},\phi_{s,3}]$ is infeasible due to intersection of $bt$
with $s$, and $\rho_{s}=\pi/2$ for
$\theta\in[0,\phi_{s,1}]\cup[\phi_{s,3},2\pi)$.

Let $\alpha_{s}$ be the angle $\theta$ of the intersection point between
$C_{\Pi}$ and the supporting line of $s$. For
$\theta\in[\phi_{s,1},\phi_{s,2}]$, $\rho_{s}(\theta)$ can be represented by a
piecewise continuous curve, which consists of at most two pieces,
corresponding to two sub-intervals $[\phi_{s,1},\alpha_{s}]$ and
$[\alpha_{s},\phi_{s,2}]$. Note that if $\phi_{s,1}\leq\alpha_{s}$, then the
curve of $\rho_{s}(\theta)$ has two pieces; otherwise, $\rho_{s}(\theta)$ is
composed of one single piece.

Let $c^{\prime}$ denote the intersection point between line segment $s$ and
the circle $D_{\Pi}$ of radius $r$ centered at $b$. In the case of
$\phi_{s,1}\leq\alpha_{s}$, for any $\theta\in[\phi_{s,1},\alpha_{s}]$, as
depicted in Figure 7B, $\rho_{s}(\theta)$ is given by the angle between $bt$
and $bc^{\prime}$. For any $\theta\in[\alpha_{s},\phi_{s,2}]$ (and
$\theta\in[\phi_{s,1},\phi_{s,2}]$ in the case of $\phi_{s,1}>\alpha_{s}$),
$\rho_{s}(\theta)$ is the angle between $bt$ and $bc^{\prime}$, where
$bc^{\prime}$ intersects an endpoint of $s$ at an interior point of
$bc^{\prime}$ (see Figure 7D). Observe that $\rho_{s}(\theta)=0$ when
$\theta=\phi_{s,2}$. A plot of function $\rho_{s}(\theta)$ is shown in Figure
8.

Figure 8: Illustration of function $\rho_{s}(\theta)$ in Case 1.

##### Case 2: $s$ lies outside $C_{\Pi}$ and inside ${C_{\Pi}}^{\prime}$

For a line segment $s$ lying outside $C_{\Pi}$ and inside
${C_{\Pi}}^{\prime}$, as depicted in Figure 9, we only need to worry about
computing $\rho_{s}$ for $\theta\in[\phi_{s,1},\phi_{s,2}]$, given that
$\rho_{s}=\pi/2$ for $\theta\in[0,\phi_{s,1}]\cup[\phi_{s,2},2\pi]$.

Figure 9: (A) Characterizing $\rho_{s}(\theta)$ for
$\theta\in[\phi_{s,1},\phi_{s,2}]$ in Case 2. Illustrations for
$\rho_{s}(\theta)$ when (B) $\phi_{s,1}<\theta<\alpha_{s}$, (C)
$\theta=\alpha_{s}$, and (D) $\alpha_{s}<\theta<\phi_{s,2}$, respectively.
Figure 10: Illustration of function $\rho_{s}(\theta)$ in Case 2.

For $\theta\in[\phi_{s,1},\phi_{s,2}]$, $\rho_{s}(\theta)$ is characterized by
a piecewise continuous curve, which consists of at most two pieces,
corresponding to sub-intervals $[\phi_{s,1},\alpha_{s}]$ and
$[\alpha_{s},\phi_{s,2}]$, where $\alpha_{s}$ is the angle $\theta$ of the
intersection point, if any, between $C_{\Pi}$ and the supporting line of $s$.
Note that if $\alpha_{s}$ exists, then $\rho_{s}(\theta)$ has two pieces;
otherwise, $\rho_{s}(\theta)$ is constituted of one single piece.

Notice that $\phi_{s,2}$ is defined differently from the previous case. Here,
$\phi_{s,2}$ is the largest $\theta$ at which the radius $bc^{\prime}$ of the
quart-sector of $\theta$ intersects with $s$ (at one of its endpoints). In
fact, when $\theta=\phi_{s,2}$, $\rho_{s}(\theta)=\pi/2$. A plot of function
$\rho_{s}(\theta)$ is shown in Figure 10.

Each of the curves $\rho_{s}(\theta)$ just described (for
$\theta\in[\phi_{s,1},\phi_{s,2}]$) is partially defined, continuous, and
monotone over $\theta$. Specifically, $\rho_{s}(\theta)$ is monotonically
decreasing (resp. increasing) with respect to $\theta$ over the range of
$[\phi_{s,1},\phi_{s,2}]$ in Case 1 (resp. Case 2). In fact, the curves behave
like pseudo-line segments, since any two curves can only intersect at most
once.

Observe that $\rho_{s}(\theta)$ is an inverse trigonometric function.
Nonetheless, we can define an algebraic function $f_{s}=\sin(\rho_{s}/2)$ in
terms of variables $x_{b}$ and $y_{b}$ (i.e., $x$\- and $y$-coordinates of
$b\in C_{\Pi}$). The details of deriving $f_{s}$ are presented next.

##### Deriving algebraic function $f_{s}$

As one shall see, we can define an algebraic function $f_{s}$ based on
$\rho_{s}(\theta)$. Recall that, in Case 1, we are only concerned with
characterizing $\rho_{s}(\theta)$ for $\theta\in[\phi_{s,1},\phi_{s,2}]$,
which consists of at most two pieces, corresponding to two sub-intervals
$[\phi_{s,1},\alpha_{s}]$ and $[\alpha_{s},\phi_{s,2}]$. Let us consider the
two sub-intervals individually. Note that, in the following analysis, $\theta$
is represented by the $x$\- and $y$-coordinates of $b\in C_{\Pi}$ (in order to
obtain an algebraic expression).

###### Sub-interval 1: $\theta\in[\phi_{s,1},\alpha_{s}]$.

For simplicity, let $\Pi$ be the $xy$-plane (in which line segment $s$ lies).
Without loss of generality, let $t$ be located at the origin. Let
$x_{c^{\prime}}$ and $y_{c^{\prime}}$ denote the $x$\- and $y$-coordinates of
$c^{\prime}$, respectively. Observe that

$\sin\frac{\rho_{s}}{2}=\frac{\sqrt{{x_{c^{\prime}}}^{2}+{y_{c^{\prime}}}^{2}}}{2r}$
(8)

Recall that $c^{\prime}$ is the intersection point between line segment $s$
and the circle $D_{\Pi}$ of radius $r$ centered at $b$ (see Figure 11). The
coordinates of $c^{\prime}$ can be expressed in terms of the coordinates of
$b$ in the following manner. Let $\ell$ be the supporting line of $s$. Line
$\ell$ can be represented by $y=mx+d$, where $m$ is the slope of $\ell$, and
$d$ is the $y$-intercept of $\ell$. Circle $D_{\Pi}$ can be formulated as
$(x–x_{b})^{2}+(y–y_{b})^{2}=r^{2}$, where $x_{b}$ and $y_{b}$ are the $x$\-
and $y$-coordinates of $b$, respectively. Then, $x_{c^{\prime}}$ and
$y_{c^{\prime}}$ can be written as

$\displaystyle x_{c^{\prime}}=\frac{x_{b}+y_{b}m+dm\pm\sqrt{\delta}}{1+m^{2}}$
(9) $\displaystyle
y_{c^{\prime}}=\frac{d+x_{b}m+y_{b}m^{2}\pm\sqrt{\delta}}{1+m^{2}}$ (10)

where $\delta=r^{2}(1+m^{2})-(y_{b}-mx_{b}-d)^{2}$. Let $f_{s}$ =
$\sin(\rho_{s}/2)$ (i.e., Equation 8). Note that $f_{s}\in[0,\sqrt{1/2}]$.
Clearly, by substituting Equations 9 and 10 into Equation 8, $f_{s}$ can be
expressed algebraically as a function of $x_{b}$ and $y_{b}$, where $b\in
C_{\Pi}$ and ${x_{b}}^{2}+{y_{b}}^{2}=r^{2}$.

Figure 11: Case for $\theta\in[\phi_{s,1},\alpha_{s}]$.

###### Sub-interval 2: $\theta\in[\alpha_{s},\phi_{s,2}]$.

Observe that Equation 8 also holds true for this sub-interval. Let $p$ be the
intersection point between $s$ and $bc^{\prime}$ (see Figure 12). Note that
$p$ is an endpoint of $s$. Let $x_{p}$ and $y_{p}$ denote the $x$\- and
$y$-coordinates of $p$. Then, $x_{c^{\prime}}$ and $y_{c^{\prime}}$ can be
expressed as

$\displaystyle
x_{c^{\prime}}=x_{b}+\sqrt{\frac{r^{2}}{1+(\frac{y_{p}-y_{b}}{x_{p}-x_{b}})^{2}}}$
(11) $\displaystyle
y_{c^{\prime}}=y_{b}+\sqrt{\frac{r^{2}}{1+(\frac{y_{p}-x_{b}}{y_{p}-y_{b}})^{2}}}$
(12)

As before, we let $f_{s}$ = $\sin(\rho_{s}/2)$, and $f_{s}$ can be expressed
algebraically as a function of $x_{b}$ and $y_{b}$ by substituting Equations
11 and 12 into Equation 8.

Figure 12: Case for $\theta\in[\alpha_{s},\phi_{s,2}]$.

A similar derivation of $f_{s}$ can also be performed in Case 2. Since
$\rho_{s}$ is partially defined, continuous, and monotone over
$\theta\in[\phi_{s,1},\phi_{s,2}]$, so must be function
$f_{s}=\sin(\rho_{s}/2)$.

At this point, we are in position to claim a new unified data structure for
solving the circular sector emptiness query problem in 2D. This
$\mathbb{R}^{2}$ data structure simplifies the two-step approach described in
[20] (which consists of a circular arc intersection query and a circular
sector emptiness query) while having the same time and space complexity.
Specifically, we construct two lower envelopes $V_{1}$ and $V_{2}$ of the
piecewise algebraic curves $f_{s}$ for all given line segments $s\in P$ as
follows: $V_{1}$ is the lower envelope of the curves $f_{s}$ for $y_{b}\geq 0$
(i.e., $0\leq\theta\leq\pi$), whereas $V_{2}$ is for $y_{b}<0$ (i.e.,
$\pi<\theta<2\pi$). Note that $V_{1}$ and $V_{2}$ are computed as functions of
$x_{b}$ only, given that $y_{b}=+(r^{2}–{x_{b}}^{2})^{1/2}$ for $y_{b}\geq 0$,
and $y_{b}=-(r^{2}–{x_{b}}^{2})^{1/2}$ for $y_{b}<0$.

Since each pair of curves $\rho_{s}$ intersect in at most one point, any two
curves $f_{s}$ do too. Thus, the size of the lower envelope is bounded by the
third-order Davenport-Schinzel sequence, whose length is at most
$O(n\alpha(n))$, where $\alpha(n)$ is the inverse Ackermann function. The
lower envelope can be computed in $O(n\log n)$ time [10, 17].

Given a query circular sector $\sigma$, let $b_{\sigma}$ be the apex of
$\sigma$. If $y_{b_{\sigma}}\geq 0$, then $x_{b_{\sigma}}$ is looked up in
$V_{1}$ by using a binary search, which takes $O(\log n)$ time; otherwise,
$x_{b_{\sigma}}$ is looked up in $V_{2}$. Let $\rho$ be the acute angle
between the two bounding radii of $\sigma$. If $\sin(\rho/2)$ is less than
$f_{s}(x_{b})$ for all line segments $s\in P$, then $\sigma$ does not
intersect $P$. Hence, we have the following result.

######  Theorem 3.4.

A set $P$ of $n$ line segments in $\mathbb{R}^{2}$ can be preprocessed in
$O(n\log n)$ time into a data structure of size $O(n\alpha(n))$ so that, for a
query circular sector $\sigma$ with a fixed radius $r$ and a fixed arc
endpoint $t$, one can determine if $\sigma$ intersects $P$ in $O(\log n)$
time.

As it turns out, we do not need to explicitly describe the function of the
lower envelope. In fact, it suffices to have an implicit representation of the
lower envelope – specifically, its vertices and the line segments that induce
its various pieces. Generally, in order to obtain an implicit representation
of the lower envelope (of a given set of curves), we require i) the number of
times each pair of curves intersect, ii) the ability to compute the
intersection points between any two given curves, and iii) the ability to
determine whether one curve lies above or below another to the left and right
of their intersection. Consider the following approach for computing an
implicit representation of the lower envelope.

##### Computing implicit lower envelopes

We only address the case of computing $V_{1}$ ($0\leq\theta\leq\pi$), and the
other case of $V_{2}$ ($\pi<\theta<2\pi$) can be handled symmetrically. Recall
that each pair of curves $f_{s}$ intersect at most once. Thus, as with
computing the lower envelope of a set of $n$ lines segments using a divide-
and-conquer algorithm, we first sort the curves $f_{s}$ by $\phi_{s,1}$. Note
that, for a given line segment $s$, $\phi_{s,1}$ can be computed without
knowing $f_{s}$, since $\phi_{s,1}$ corresponds to the smallest angle $\theta$
at which the circle of radius $r$ centered at $b\in C_{\Pi}$ intersects with
$s$. We divide the set of curves $f_{s}$ into two equal sets by $\phi_{s,1}$,
recursively compute the lower envelope of each set, and then merge the two
lower envelopes to obtain the final result. The intersection of any two curves
$f_{s_{i}}$ and $f_{s_{j}}$ (which correspond to line segments $s_{i}$ and
$s_{j}$, respectively) can be determined as follows. There are two cases to be
considered, depending on how $bc^{\prime}$ is supported by $s_{i}$ and
$s_{j}$.

###### Case A.

Line segment $bc^{\prime}$ intersects $s_{i}$ and $s_{j}$ at their endpoints
(see Figure 13). Note that the corresponding $x_{b}$ can be computed
algebraically, given that $b$ is the intersection point between $C_{\Pi}$ and
$bc^{\prime}$. Specifically, $C_{\Pi}$ can be represented as
$x^{2}+y^{2}=r^{2}$. Let $p$ and $q$ denote the endpoints of $s_{i}$ and
$s_{j}$, respectively, that intersect $bc^{\prime}$. Then, the line that
passes through $p$ and $q$ can be expressed as $y=m_{pq}x+d_{pq}$, where
$m_{pq}=(y_{q}-y_{p})/(x_{q}-x_{p})$ and
$d_{pq}=y_{p}-[(y_{q}-y_{p})/(x_{q}-x_{p})]x_{p}$. Hence,

$x_{b}=\frac{-d_{pq}m_{pq}\pm\sqrt{\delta_{pq}}}{1+{m_{pq}}^{2}}$

where $\delta_{pq}=r^{2}(1+{m_{pq}}^{2})-{d_{pq}}^{2}$. We can also decide in
constant time (based on the slope of $bc^{\prime}$) which of the two curves
$f_{s_{i}}$ and $f_{s_{j}}$, to the left and right of their intersection at
$x_{b}$, lies above/below the intersection point. For instance, in the example
illustrated in Figure 13, we can easily determine that $f_{s_{j}}$ lies below
(resp. above) $f_{s_{i}}$ to the left (resp. right) of their intersection at
$x_{b}$.

Figure 13: Case A.

###### Case B.

Line segment $bc^{\prime}$ intersects $s_{i}$ such that $c^{\prime}$ coincides
with an interior point of $s_{i}$, and intersects $s_{j}$ at its endpoint (see
Figure 14). As with the previous case, we can compute the corresponding
$x_{b}$ algebraically. Let $\ell$ denote the supporting line of $s_{i}$, and
let $q$ be the intersection point between $s_{j}$ and $bc^{\prime}$. Line
$\ell$ can be expressed as $y=m_{\ell}x+d_{\ell}$. Observe that the line
passing through $c^{\prime}$ and $q$ intersects $C_{\Pi}$ at $b$; let the line
be represented as $y=m_{c^{\prime}q}x+d_{c^{\prime}q}$. Then,

$\displaystyle
x_{b}=\frac{-d_{c^{\prime}q}m_{c^{\prime}q}\pm\sqrt{\delta_{c^{\prime}q}}}{1+{m_{c^{\prime}q}}^{2}}$
(13) $\displaystyle y_{b}=\frac{d_{c^{\prime}q}\pm
m_{c^{\prime}q}\sqrt{\delta_{c^{\prime}q}}}{1+{m_{c^{\prime}q}}^{2}}$ (14)

where $m_{c^{\prime}q}=(y_{q}-y_{c^{\prime}})/(x_{q}-x_{c^{\prime}})$,
$d_{c^{\prime}q}=y_{c^{\prime}}-[(y_{q}-y_{c^{\prime}})/(x_{q}-x_{c^{\prime}})]x_{c^{\prime}}$,
and
$\delta_{c^{\prime}q}=r^{2}(1+{m_{c^{\prime}q}}^{2})-{d_{c^{\prime}q}}^{2}$.
Since the circle of radius $r$ centered at $b$ intersects $\ell$ at $c$,

$\displaystyle
x_{c^{\prime}}=\frac{x_{b}+y_{b}m_{\ell}+dm_{\ell}\pm\sqrt{\delta_{\ell}}}{1+{m_{\ell}}^{2}}$
(15) $\displaystyle
y_{c^{\prime}}=\frac{d_{\ell}+x_{b}m_{\ell}+y_{b}{m_{\ell}}^{2}\pm\sqrt{\delta_{\ell}}}{1+{m_{\ell}}^{2}}$
(16)

where
$\delta_{\ell}=r^{2}(1+{m_{\ell}}^{2})-(y_{b}-{m_{\ell}}x_{b}-d_{\ell})^{2}$.
Clearly, we can determine $x_{b}$ by using Equations 13–16. As before, we can
also decide in $O(1)$ time which of the two curves $f_{s_{i}}$ and
$f_{s_{j}}$, to the left and right of their intersection at $x_{b}$, lies
above/below the intersection point.

Figure 14: Case B.

Notice that we did not compute a full (functional) description of the lower
envelope. Instead, for each piece of the lower envelope, we store the
information about the line segment $s$ associated with the curve $f_{s}$ to
which the piece of the lower envelope belongs.

At query time, given a circular sector $\sigma$ (and its associated $x_{b}$),
we can determine if $\sigma$ intersects any line segment in $P$, without
having to know the equation for the curve $f_{s}$ defining the lower envelope
at $x_{b}$, as follows. We retrieve the line segment $s$ that induces the
curve $f_{s}$ defining the lower envelope at $x_{b}$, and check if $bc$ of
$\sigma$ intersects $s$. If $bc$ of $\sigma$ does not intersect $s$, then
$\sigma$ does not intersect $P$.

We now continue to derive our result for circular sector emptiness queries in
3D. For each triangle $\tau\in P$, we define a trivariate function
$\rho_{\tau}(I,\Omega,\theta)$, so that $\rho_{s}(\theta)$ is characterized
with respect to all planes $(I,\Omega)$. As with the two-dimensional case,
$\rho_{\tau}(I,\Omega,\theta)$ is an inverse trigonometric function, based on
which we can define an algebraic function $f_{\tau}$ (of constant degree) in
terms of four variables as follows.

##### Deriving algebraic function $f_{\tau}$

In the following analysis, Cartesian variables are used in place of $I$,
$\Omega$, and $\theta$, in order to derive an algebraic expression for
$f_{\tau}$. As with characterizing the univariate function $\rho_{s}(\theta)$,
there are two cases to be considered, depending on whether a given triangle
$\tau$ is located 1) inside sphere $C$ or 2) outside sphere $C$ and inside
sphere $C^{\prime}$. Given the similarity in analysis between the two cases,
we only present the details for Case 1. As before, we are concerned with
computing $\rho_{\tau}$ for two contiguous sub-intervals of
$(I,\Omega,\theta)$. In one of the sub-intervals, $bc^{\prime}$ always
intersects the interior of $\tau$ at $c^{\prime}$. In the other sub-interval,
$bc^{\prime}$ intersects an edge of $\tau$. Let us examine the two sub-
intervals individually.

###### Sub-interval 1: $bc^{\prime}$ intersects the interior of $\tau$ at
$c^{\prime}$.

Without loss of generality, let $t$ be located at the origin. Let
$x_{c^{\prime}}$, $y_{c^{\prime}}$, and $z_{c^{\prime}}$ denote the $x$-,
$y$-, and $z$-coordinates of $c^{\prime}$, respectively. Observe that

$f_{\tau}=\sin\frac{\rho_{\tau}}{2}=\frac{\sqrt{{x_{c^{\prime}}}^{2}+{y_{c^{\prime}}}^{2}+{z_{c^{\prime}}}^{2}}}{2r}$
(17)

Let $G$ be the plane passing through points $t$ and $b$. Plane $G$ can be
represented as $g_{1}x+g_{2}y+g_{3}z+g_{4}=0$, where $g_{4}=0$ and
$g_{3}=(-g_{1}x_{b}-g_{2}y_{b})/z_{b}$. If we define $g=g_{1}/g_{2}$, then the
expression for $G$ becomes $gx+y+[(-g_{1}x_{b}-g_{2}y_{b})/z_{b}]z=0$. Given
that $G$ contains $c^{\prime}$,

$gx_{c^{\prime}}+y_{c^{\prime}}+\left(\frac{-g_{1}x_{b}-g_{2}y_{b}}{z_{b}}\right)z_{c^{\prime}}=0$
(18)

Let $H$ be the supporting plane of $\tau$. Plane $H$ can be expressed as
$h_{1}x+h_{2}y+h_{3}z+h_{4}=0$, where $h_{1}$, $h_{2}$, $h_{3}$, and $h_{4}$
are the known parameters determined based on the three vertices of $\tau$.
Since $H$ contains $c^{\prime}$,

$h_{1}x_{c^{\prime}}+h_{2}y_{c^{\prime}}+h_{3}z_{c^{\prime}}+h_{4}=0$ (19)

Notice that $|bc^{\prime}|=r$. Thus,

$(x_{c^{\prime}}-x_{b})^{2}+(y_{c^{\prime}}-y_{b})^{2}+(z_{c^{\prime}}-z_{b})^{2}=r^{2}$
(20)

Based on the three Equations 18, 19, and 20, we can obtain an algebraic
expression for $x_{c^{\prime}}$, $y_{c^{\prime}}$, and $z_{c^{\prime}}$,
respectively, in terms of variables $g$, $x_{b}$, $y_{b}$, and $z_{b}$. By
substituting the resulting algebraic expressions for $x_{c^{\prime}}$,
$y_{c^{\prime}}$, and $z_{c^{\prime}}$ into Equation 17, $f_{\tau}$ can be
expressed algebraically as a function (of degree one) of $g$, $x_{b}$,
$y_{b}$, and $z_{b}$, where $b\in C$ and
${x_{b}}^{2}+{y_{b}}^{2}+{z_{b}}^{2}=r^{2}$.

###### Sub-interval 2: $bc^{\prime}$ intersects an edge of $\tau$.

Let $s$ denote the edge of $\tau$ intersected by $bc^{\prime}$. Edge $s$ can
be expressed in parametric form as

$\displaystyle x=(1-\lambda_{s})x_{u}+\lambda_{s}x_{v}$ $\displaystyle
y=(1-\lambda_{s})y_{u}+\lambda_{s}y_{v}$ $\displaystyle
z=(1-\lambda_{s})z_{u}+\lambda_{s}z_{v}$

where $u$ and $v$ are the two endpoints of $s$, and $0\leq\lambda_{s}\leq 1$.
Let $p$ denote the intersection point between $bc^{\prime}$ and $s$. The
supporting line $\ell$ of $bc^{\prime}$ can be represented as

$\displaystyle x=(1-\lambda_{\ell})x_{b}+\lambda_{\ell}x_{p}$ $\displaystyle
y=(1-\lambda_{\ell})y_{b}+\lambda_{\ell}y_{p}$ $\displaystyle
z=(1-\lambda_{\ell})z_{b}+\lambda_{\ell}z_{p}$

where $\lambda_{\ell}\in\mathbb{R}$. Given that $p$ lies in $s$, and $\ell$
contains $c^{\prime}$,

$\displaystyle
x_{c^{\prime}}=(1-\lambda_{\ell})x_{b}+\lambda_{\ell}[(1-\lambda_{s})x_{u}+\lambda_{s}x_{v}]$
(21) $\displaystyle
y_{c^{\prime}}=(1-\lambda_{\ell})y_{b}+\lambda_{\ell}[(1-\lambda_{s})y_{u}+\lambda_{s}y_{v}]$
(22) $\displaystyle
z_{c^{\prime}}=(1-\lambda_{\ell})z_{b}+\lambda_{\ell}[(1-\lambda_{s})z_{u}+\lambda_{s}z_{v}]$
(23)

Note that Equation 20 still applies in this case. Substitute Equations 21, 22,
and 23 into Equation 20, and solve for $\lambda_{\ell}$ in respect of
variables $\lambda_{s}$, $x_{b}$, $y_{b}$, and $z_{b}$. Then, by substituting
the resulting expression for $\lambda_{\ell}$ into Equations 21, 22, and 23,
we obtain an algebraic expression (of degree one) for $x_{c^{\prime}}$,
$y_{c^{\prime}}$, and $z_{c^{\prime}}$, respectively, in terms of variables
$\lambda_{s}$, $x_{b}$, $y_{b}$, and $z_{b}$.

At last, by substituting the algebraic expressions for $x_{c^{\prime}}$,
$y_{c^{\prime}}$, and $z_{c^{\prime}}$ into Equation (17), $f_{\tau}$ can be
expressed algebraically as a function of $\lambda_{s}$, $x_{b}$, $y_{b}$, and
$z_{b}$, where $b\in C$ and ${x_{b}}^{2}+{y_{b}}^{2}+{z_{b}}^{2}=r^{2}$.

##### Finishing up

We construct two lower envelopes $V_{1}$ and $V_{2}$ of the piecewise
algebraic functions $f_{\tau}$ for all given triangles $\tau\in P$, such that
$V_{1}$ is the lower envelope of $f_{\tau}$ for $z_{b}\geq 0$, and $V_{2}$ is
for $z_{b}<0$. As a result, $V_{1}$ and $V_{2}$ are functions of only three
variables.

For constructing the lower envelope of the trivariate piecewise algebraic
functions (of constant description complexity) just described, the best-known
performance bounds are given by Koltun [12] and Agarwal et al. [1].
Specifically, according to Koltun [12], we can compute the lower envelope
deterministically in $O(n^{4+\epsilon})$ time and store it in a data structure
of size $O(n^{4+\epsilon})$ and query time $O(\log n)$, for any $\epsilon>0$.
On the other hand, Agarwal et al. [1] showed that the lower envelope can be
constructed in randomized expected time $O(n^{3+\epsilon})$ and stored in an
$O(n^{3+\epsilon})$-size data structure with a query time of $O(\log^{2}n)$.
Thus, we arrive at the result below.

######  Theorem 3.5.

For any constant $\epsilon>0$, a set $P$ of $n$ triangles in $\mathbb{R}^{3}$
can be preprocessed in $O(n^{4+\epsilon})$ time into a data structure of size
$O(n^{4+\epsilon})$ so that, for a query circular sector $\sigma$ with a fixed
radius $r$ and an endpoint of its arc located at fixed point $t$, one can
determine whether $\sigma$ intersects $P$ in $O(\log n)$ time.

Given that $O(n^{4})$ queries are to be processed in the worst case, the
following result is obtained.

######  Lemma 3.6.

A feasible articulated probe trajectory, if one exists, can be determined in
$O(n^{4+\epsilon})$ time using $O(n^{4+\epsilon})$ space, for any constant
$\epsilon>0$.

Since the space/time complexity of finding an extremal feasible articulated
trajectory (Lemma 3.6) is dominant over that of the case of unarticulated
trajectory (Lemma 3.3), the final result can be stated as follows.

######  Theorem 3.7.

One can determine if a feasible trajectory exists, and if so, report (at
least) one such trajectory in $O(n^{4+\epsilon})$ time using
$O(n^{4+\epsilon})$ space, for any constant $\epsilon>0$.

As an alternative, an $O(n^{5})$-time algorithm with linear space usage is
achievable by performing a simple $O(n)$-check on each of the $O(n^{4})$
extremal trajectories. The proposed enumeration algorithm is easy to implement
and could be quite fast in practice, since the enumeration stops once a
feasible solution is found. In addition, given that an extremal feasible probe
trajectory amid $n$ line segment obstacles in the plane can be obtained in
$O(n^{2})$ time [8], one could use a sampling-based method to find a feasible
probe trajectory among $n$ triangular obstacles in 3D space. Specifically, one
could generate a finite set of planes passing through fixed point $t$ either
randomly or using an appropriate discretization scheme (i.e., with respect to
parameters $I$ and $\Omega$), and then employ the existing data structure from
[20] to compute the set of feasible trajectories, if any, in each plane.

##  4 Conclusion

We have presented efficient data structures and algorithms for solving a
trajectory planning problem involving a simple articulated probe in 3D space.
In particular, we have shown that a feasible probe trajectory, among $n$
triangular obstacles, can be found in $O(n^{4+\epsilon})$ time, for any
constant $\epsilon>0$. In the process, we have solved a special case of the
circular sector emptiness query problem in 3D and simplified the corresponding
data structure in 2D. We leave open the following questions: 1) Since our
approach is enumerative, can we speed up the process of finding one feasible
solution? 2) Is it possible to extend the current algorithm to finding
feasible probe trajectories of a given (or maximum) clearance?

## Acknowledgment

The authors would like to thank Pankaj K. Agarwal for helpful discussions and
comments.

## References

  * Agarwal et al. [1997] Agarwal, P.K., Aronov, B., Sharir, M., 1997.  Computing envelopes in four dimensions with applications.  SIAM Journal on Computing 26, 1714–1732.
  * Agarwal and Matousek [1994] Agarwal, P.K., Matousek, J., 1994\.  On range searching with semialgebraic sets.  Discrete & Computational Geometry 11, 393–418.
  * de Berg et al. [1994] de Berg, M., Halperin, D., Overmars, M., Snoeyink, J., van Kreveld, M., 1994.  Efficient ray shooting and hidden surface removal.  Algorithmica 12, 30–53.
  * Biedl et al. [2001] Biedl, T., Demaine, E., Demaine, M., Lazard, S., Lubiw, A., O’Rourke, J., Overmars, M., Robbins, S., Streinu, I., Toussaint, G., et al., 2001\.  Locked and unlocked polygonal chains in three dimensions.  Discrete & Computational Geometry 26, 269–281.
  * Brooks and Lozano-Perez [1985] Brooks, R.A., Lozano-Perez, T., 1985\.  A subdivision algorithm in configuration space for findpath with rotation.  IEEE Transactions on Systems, Man, and Cybernetics SMC-15, 224–233.
  * Choset et al. [2005] Choset, H.M., Hutchinson, S., Lynch, K.M., Kantor, G., Burgard, W., Kavraki, L.E., Thrun, S., 2005.  Principles of robot motion: theory, algorithms, and implementation.  MIT Press.
  * Connelly and Demaine [2017] Connelly, R., Demaine, E.D., 2017\.  Geometry and topology of polygonal linkages.  Handbook of Discrete and Computational Geometry , 233–256.
  * Daescu and Teo [2020] Daescu, O., Teo, K.Y., 2020\.  Characterization and computation of feasible trajectories for an articulated probe with a variable-length end segment, in: 32nd Annual Canadian Conference on Computational Geometry.
  * Donald [1984] Donald, B.R., 1984.  Motion planning with six degrees of freedom.  Technical Report. MIT Artificial Intelligence Lab.
  * Hershberger [1989] Hershberger, J., 1989.  Finding the upper envelope of n line segments in O(n log n) time.  Information Processing Letters 33, 169–174.
  * Kavraki et al. [1996] Kavraki, L., Svestka, P., Latombe, J., Overmars, M., 1996\.  Probabilistic roadmaps for path planning in high-dimensional configuration spaces.  IEEE Transactions on Robotics and Automation 12, 566–580.
  * Koltun [2004] Koltun, V., 2004.  Almost tight upper bounds for vertical decompositions in four dimensions.  Journal of the ACM 51, 699–730.
  * LaValle [2006] LaValle, S.M., 2006.  Planning algorithms.  Cambridge University Press.
  * LaValle and Kuffner Jr [2001] LaValle, S.M., Kuffner Jr, J.J., 2001\.  Randomized kinodynamic planning.  The International Journal of Robotics Research 20, 378–400.
  * McKenna [1987] McKenna, M., 1987.  Worst-case optimal hidden-surface removal.  ACM Transactions on Graphics 6, 19–28.
  * Pellegrini [1993] Pellegrini, M., 1993.  Ray shooting on triangles in 3-space.  Algorithmica 9, 471–494.
  * Sharir and Agarwal [1995] Sharir, M., Agarwal, P.K., 1995\.  Davenport-Schinzel sequences and their geometric applications.  Cambridge University Press.
  * Sharir and Shaul [2011] Sharir, M., Shaul, H., 2011\.  Semialgebraic range reporting and emptiness searching with applications.  SIAM Journal on Computing 40, 1045–1074.
  * Simaan et al. [2018] Simaan, N., Yasin, R.M., Wang, L., 2018.  Medical technologies and challenges of robot-assisted minimally invasive intervention and diagnostics.  Annual Review of Control, Robotics, and Autonomous Systems 1, 465–490.
  * Teo et al. [2020] Teo, K.Y., Daescu, O., Fox, K., 2020.  Trajectory planning for an articulated probe.  Computational Geometry , 101655.
  * Yakey et al. [2001] Yakey, J.H., LaValle, S.M., Kavraki, L.E., 2001.  Randomized path planning for linkages with closed kinematic chains.  IEEE Transactions on Robotics and Automation 17, 951–958.
  * Zhu and Latombe [1990] Zhu, D., Latombe, J., 1990.  Constraint reformulation in a hierarchical path planner, in: Proceedings of the IEEE International Conference on Robotics and Automation, IEEE. pp. 1918–1923.