TITLE: The functions $f(x)$ and $g(x)$ satisfy $f(0) = 3,$ $g(0) = -4,$ and $f'(x) = 7f(x) + 2g(x)$ and $g'(x) = -4f(x) + g(x).$ Find $f(x).$
QUESTION [0 upvotes]: The functions $f(x)$ and $g(x)$ satisfy $f(0) = 3,$ $g(0) = -4,$ and
\begin{align*}
f'(x) &= 7f(x) + 2g(x), \\
g'(x) &= -4f(x) + g(x).
\end{align*}Find $f(x).$
I'm not sure how to solve the following system of equations, could someone please help? I got the general form of $f(x)$ to be $(c_1+2c_2)e^{5x}-(c_1+c_2)e^{3x}$ for constants $c_1$ and $c_2$, but I'm not sure how to find these constants using the initial conditions. Thanks!

REPLY [1 votes]: What you do is set up a system of equations by applying the initial conditions, as jDAQ mentioned. Before setting up the equations, I will just mention that you should also include $g(x):$
\begin{align*}
f(x)&=(c_1+2c_2)e^{5x}-(c_1+c_2)e^{3x}\\
g(x)&=-(c_1+2c_2)e^{5x}+2(c_1+c_2)e^{3x}.
\end{align*}
Here's how it would look:
\begin{align*}
f(0)&=3\\
g(0)&=-4\\
(c_1+2c_2)-(c_1+c_2)&=3\\
-(c_1+2c_2)+2(c_1+c_2)&=-4\\
c_2&=3\\
c_1&=-4.
\end{align*}
Then just re-write $f$ and $g$ with these values plugged in.


TITLE: How to obtain the bound $\lambda \exp(\lambda^{2}/2)$
QUESTION [1 upvotes]: How is the the bound $$ \int _{0}^{\infty} \frac{e^{-x^{2}/2}}{\sqrt{2\pi}} x(\exp(\lambda x)-1)dx \leq \lambda \exp(\lambda^{2} /2)$$ obtained for $\lambda > 0$?
Splitting the integral does not help since $E[X\mathbb 1_{\{X \geq 0\}}] $ is infinite is $X$ is standard normal Gaussian. Furthermore, I know that:
$\lambda x \leq \exp(\lambda x)-1$.
The only way I could use this would be to say
$$ \int _{0}^{\infty} \frac{e^{-x^{2}/2}}{\sqrt{2\pi}} x(\exp(\lambda x)-1)dx \leq \int_{0}^{\infty}\frac{(\exp(\lambda x )-1)^{2}}{\lambda}\frac{e^{-x^{2}/2}}{\sqrt{2\pi}}dx$$
Any ideas?

REPLY [1 votes]: Maybe it's a printing or copying error but you can show the estimation using $\sqrt{2\pi}$ instead of $2\pi$ by partial integration:
\begin{eqnarray*} \int _{0}^{\infty} \underbrace{\frac{e^{-x^{2}/2}}{\sqrt{2\pi}} x}_{u'} \underbrace{(\exp(\lambda x)-1)}_{v}dx
& = & \underbrace{\left. -\frac{e^{-x^{2}/2}}{\sqrt{2\pi}}(\exp(\lambda x)-1)\right|_0^{\infty} }_{=0}+ \frac{\lambda}{\sqrt{2\pi}} \int _{0}^{\infty}e^{-\frac{x^2}{2}+\lambda x} dx \\
& \stackrel{square\: compl.}{=} & \frac{\lambda}{\sqrt{2\pi}}\int _{0}^{\infty}e^{-\frac{(x-\lambda)^2-\lambda^2}{2}} dx \\
& \stackrel{t=x-\lambda}{=} & \frac{\lambda e^{\frac{\lambda^2}{2}}}{\sqrt{2\pi}} \int _{\color{blue}{-\lambda}}^{\infty}e^{-\frac{t^2}{2}} dt \\
& \stackrel{\int_{-\infty}^{\infty}e^{-\frac{t^2}{2}} dt = \sqrt{2\pi}}{\leq} & \lambda e^{\frac{\lambda^2}{2}}
\end{eqnarray*}


text:
\begin{document}

\title{Energy-efficient motion camouflage in three dimensions}
\author{N.E. Carey, M.V. Srinivasan}
\date{}
\maketitle

\abstract{Recent observations suggest that one insect may camouflage
its own motion whilst tracking another. Here we present a strategy
by which one agent can efficiently track and intercept another
agent, whilst camouflaging its own motion and minimizing its energy
consumption.}

\section{Introduction}
The past decade has witnessed increasing interest  in a phenomenon
known as `motion camouflage' -- a term coined by Srinivasan and
Davey (1996) to explain a class of interactive manoeuvres in
hoverflies, observed by Collett and Land (1975). Srinivasan and
Davey noted that, in certain circumstances, one hoverfly (A) would
`shadow' another hoverfly (B) by moving in such a way as to mimic
the optic flow that would be produced by a stationary object in B's
retina, thus `camouflaging' its own motion and escaping detection.
As illustrated in Fig. 1, A (the shadower) tracks B (the shadowee)
by moving in such a way that A always remains on a straight line
connecting B with a fixed, stationary point (S) in the environment.
If A moves in this way, the trajectory of its image will be
indistinguishable from the trajectory produced by a stationary
object located at S. The lines connecting the shadowee to the fixed
point are termed `camouflage constraint lines' (CCLs), because
successive positions of the shadower are constrained to lie on these
lines if motion camouflage is to be maintained. This analysis
assumes that A is small enough or sufficiently far away from B that
that it appears as a point object in B's retina, and thus does not
create any noticeable image expansion or contraction.

\begin{figure}[ht!]
\begin{center}
\subfigure[Static Point Camouflage, static point
behind]{\label{fig:demo1}
\includegraphics[width=4cm]{camo_diag1}}
\hspace{.3in} \subfigure[Static Point Camouflage, static point
between]{\label{fig:demo3}
\includegraphics[width=4cm]{camo_diag3}}
\hspace{.3in} \subfigure[Infinite Point
Camouflage]{\label{fig:demo2}
\includegraphics[width=4cm]{camo_diag2}}
\caption{Depiction of the primary types of motion camouflage}
\end{center}
\end{figure}
How should an animal move if it is to minimize energy consumption
(for example), or interception time, whilst camouflaging its motion?
In general, such trajectories can be calculated only if the
trajectory of the shadowee is known, or can be reliably predicted
\cite{Carey}, \cite{Srini}. Anderson and McOwen \cite{Model} tackled
this limitation by training artificial neural networks to control
simulated shadowers. Their design used a control system formed from
three separate neural networks, and calculated a control command
based upon the distance from the chosen static point, the direction
required for camouflage maintenance, and the line-of-sight error
angle to the target. However the usual limitations of neural network
solutions still applied. An exploration of the entire state-space
was necessary prior to commencement of the learning period for the
networks. The resulting controller was tailored to a specific type
of shadowee trajectory, and lost performance quality when
encountering unexpected varieties of motion.

A more traditional approach is to create a linear quadratic feedback
controller to govern the behaviour of the shadowee  \cite{Carey}.
The deviation of the shadower's trajectory from that dictated by the
CCLs (in two dimensions) is used in conjunction with a weighted
penalty on control action to create a cost function that results in
a stable feedback controller. However, without a limit placed on the
maximum control effort that could be requested, the required control
acceleration can be very large, especially if a shadowee executes a
trajectory that is highly non-linear. And placing a realistic cap on
the control commands compromises the accuracy of the resulting
trajectory. Moreover, such a controller is a) not biologically
realistic and b) designed to perform on a predictable shadowee path.
Erratic or non-predictable paths are very calculation-intensive, as
the solution has to be recalculated for each movement made by the
shadowee.

Reddy et al.  explored dynamic models in both two \cite{Krishna1}
and three \cite{Krishna2} dimensions, restricting the case to motion
camouflage where the shadower emulates a fixed point that is
infinitely far away. Their research was inspired by insect-capture
behaviour in echo-locating bats. They modelled the shadower and
shadowee as points subject to curvature control, rather than speed
control (as is more traditional). They derived a feedback control
law for motion camouflage using neural networks, which they called
'motion camouflage proportional guidance' \cite{Krishna1}, and then
extended this planar guidance law to three dimensions, describing
the particle trajectories using natural Frenet frames
\cite{Krishna1}, \cite{Krishna3}.

Motivated by the work of \cite{Srini} and \cite{akiko}, Glendinning
\cite{Glendinning} developed an explicit mathematical description of
the geometry governing a motion camouflaged interaction. While an
infinite number of potential camouflage paths exist for any given
prey trajectory, his analysis allows us to prescribe further
constraints on the behaviour of the shadower, that can give rise to
a unique solution.

Here we present a method for devising 3-dimensional trajectories
which not only achieve perfect motion camouflage but do so in an
energy-efficient manner. This approach will be useful in the design
of energy-optimal controllers.

\section{Background}
Glendinning \cite{Glendinning} characterized motion camouflaged
paths mathematically in the following way.  In 3-D Cartesian space,
let $\mathbf{r}_D(t)$ and $\mathbf{r}_T(t)$ be the vectors
representing the time-varying paths of the pursuer and the target,
respectively, and let $\mathbf{r}_P$ be the vector that represents
the position of the fixed point.   The camouflage constraint then
requires that, at all times $t$,
\begin{equation}
\mathbf{r}_D(t) = \mathbf{r}_D(0) + k(t)(\mathbf{r}_T(t) -
\mathbf{r}_P) \nonumber ,
\end{equation}
ie
\begin{equation}
\mathbf{r}_P - \mathbf{r}_D(t) = k(t) \left( \mathbf{r}_P -
\mathbf{r}_T (t) \right) \quad \forall \quad  t >0 \label{equ:first}
\end{equation}
where $\lbrace k(t) \lVert  -\infty < k(t) \leq 1 \rbrace$ is a
continuous time-varying scalar function. Positive $k(t)$ corresponds
to figure \ref{fig:demo1}, negative $k(t)$ corresponds to figure
\ref{fig:demo3}. (Infinite point camouflage, as in figure \ref{fig:demo2},
requires a slightly different formulation, as discussed in section
\ref{sec:infcam}).

This equation is simply a quantitative statement of the requirement
that the pursuer should always be located on the straight line
connecting the target to the fixed point. $k$ may be thought of as
representing the ratio in range between the shadowee and shadower,
with reference to the static point $P$, at any time $t$. Since
$k(t)$ can be any (bounded) continuous function, there are
infinitely many trajectories that will satisfy the requirement of
motion camouflage. The task of the analyst, then, is to determine
constraints which lead to a unique path description. For example, we
may require interception to occur in minimum time, or, as in this
paper, with minimum expenditure of energy.

\section{Procedure}
\subsection{Camouflage with a non-infinite static point}
We assume the function $k(t)$ to be twice differentiable, and that
the initial conditions of the system are known. As is traditional,
we ignore any gravitational effects. We then take an energy
minimization approach to finding an optimal path, using Lagrangian
mechanics. In classical and quantum mechanics, equations of motion
are derived from what is termed the 'principle of least action'.
`Action' is a quantity which has dimensions of energy integrated
over time. The energy in question is expressed by an equation known
as the Lagrangian, and is generally taken as being the kinetic
energy of the system minus its potential energy. Let the transpose
of a vector $\mathbf{x}$ be represented as $\mathbf{x}^\prime$, then
assuming a particle of unit mass, the Lagrangian for the
motion-camouflaged system can be written as
\begin{equation}
\mathcal{L} = KE - PE = \frac{1}{2} \mathbf{\dot{r}}_D^\prime
\mathbf{\dot{r}_D} \label{equ:onetwo}
\end{equation}
ie kinetic energy minus potential energy \cite{Lagrangian} (note
that since we are ignoring any gravitational force, the potential
energy term can be neglected). By solving the Euler-Lagrange
equations for such a system, we can use Hamilton's Principle of
Least Action \cite{Bertsekas2} to find the path the particle will
take if no other forces are acting on it besides those required to
keep the motion camouflaged. To accomplish this, we set the system
cost to be the integral of the Lagrangian,
\begin{equation}
J = \frac{1}{2} \int_{t_0}^{t}{\dot{\mathbf{r}}_D^\prime
\dot{\mathbf{r}}_D } dt \label{equ: onethree}
\end{equation}

Differentiating equation (\ref{equ:first}) with respect to time, we
obtain
\begin{equation}
-\dot{\mathbf{r}}_D(t) = \dot{k}(t)(\mathbf{r}_P - \mathbf{r}_T(t)) - k(t) \dot{\mathbf{r}}_T(t) \label{equ:two}
\end{equation}
Since $k(t)$ parameterizes the path of the shadower, finding an
appropriate stationary value for the energy curve
\begin{equation}
\frac{1}{2} \int_{t_0}^{t}{ \dot{\mathbf{r}}_D(t)^\prime
\dot{\mathbf{r}}_D(t)} dt \label{equ:three}
\end{equation}
is equivalent to finding the function $k(t)$ such that the quantity
\begin{equation}
\frac{1}{2} \int_{t_0}^{t} \left[ k(t) \dot{\mathbf{r}}_T(t) -
\dot{k}(t)(\mathbf{r}_P - \mathbf{r}_T(t) \right]^\prime \big[ k(t)
\dot{\mathbf{r}}_T(t) - \dot{k}(t)(\mathbf{r}_P - \mathbf{r}_T(t)
\big] dt \label{equ:four}
\end{equation}
is minimised. We do this by solving the Euler-Lagrange (E-L)
equation \cite {Lagrangian}. With $\mathcal{L}$ as before, the E-L
equation for the system is
\begin{equation}
\frac{\partial \mathcal{L}}{\partial k} - \frac{d}{dt}
\frac{\partial \mathcal{L}}{\partial \dot{k}} = 0 \label{equ:five}.
\end{equation}
Expanding this, we obtain a second-order differential equation in
$k$:
\begin{equation}
\ddot{k} \left[ (\mathbf{r}_P - \mathbf{r}_T)^\prime(\mathbf{r}_P -
\mathbf{r}_T) \right] +  2 (-\dot{k} \left[
\dot{\mathbf{r}}_T^\prime (\mathbf{r}_P - \mathbf{r}_T) \right]) +
 k \left[ -\ddot{\mathbf{r}}_T^\prime (\mathbf{r}_P - \mathbf{r}_T) \right]= 0 .
\label{equ:nine}
\end{equation}
Setting $(\mathbf{r}_P-\mathbf{r}_T(t))=\mathbf{\alpha}(t)$, we can
write (\ref{equ:nine}) as:
\begin{equation}
\ddot{k} \alpha^\prime \alpha + 2\dot{k}\dot{\alpha}^\prime \alpha +
k\ddot{\alpha}^\prime \alpha =0 \label{equ:eleven} .
\end{equation}
In other words, \begin{equation} \left( \frac{d^2}{dt^2} (k \alpha)
\right) \cdot \alpha = 0 \label{equ:main},
\end{equation}
hence we can state that $k(t)$ will satisfy the Lagrangian
conditions when the acceleration of the pursuer is orthogonal to the
line-of-sight vector between the pursuer and target.

This ODE does not have a general analytical solution, but it is
amenable to numerical solution methods. Moreover, given further
information about the target path, we can develop analytical
solutions. In the following sections, we will primarily focus on the
homogenous solution, which occurs when the target travels in a
straight line at constant velocity, however some attention will be
paid to other quantifiable target trajectories.

\subsection{Camouflage at Infinity} \label{sec:infcam}
A similar method can be used to generate optimal paths with
camouflage at infinity \cite{Srini}. We again use a general
formulation given by Glendinning \cite{Glendinning}:
\begin{equation}
\mathbf{r}_T - \mathbf{r}_D = k(t) \mathbf{e} \label{equ:eighteen}
\end{equation}
where $\mathbf{e}$ is a constant vector. For the sake of simplicity,
we choose $\mathbf{e}$ to correspond with the initial conditions, so
\begin{equation}
\mathbf{e} = \mathbf{r}_T (t_0) - \mathbf{r}_D (t_0) .
\end{equation}
Differentiating and applying the same cost function as before, we
obtain the Lagrangian and develop a solution. Fortunately, the
Euler-Lagrange equation for camouflage at infinity is solvable
analytically, and we find the function $k(t)$ has a general solution
of the form
\begin{equation}
k \mathbf{e}^T \mathbf{e} = \mathbf{r}_T ^T\mathbf{e} + c_1 t + c_2
\label{equ:twentytwo}
\end{equation}
for some constants of integration $c_1, c_2$.

\section{Examples of optimal motion camouflage equations}
With more information about the target trajectory, we can simplify
the problem and discover an analytic solution. In this section, we
present a few examples of optimal motion camouflage against targets
with various dynamic characteristics.

\subsection{Camouflage against a target moving at constant
velocity} We begin by assuming that the target moves in a straight
line at constant velocity, ie $\ddot{\mathbf{r}}_T=0$. Solving
equation (\ref{equ:main}) is then equivalent to solving the
second-order homogenous differential equation
\begin{equation}
\frac{d^2}{dt^2}(k \lVert \alpha \rVert) = 0 \label{equ:filler} .
\end{equation}

Equation \ref{equ:filler} has a solution of the form
\begin{equation}
k \lVert \alpha \rVert = c_1 t + c_2 \label{equ:twelve}
\end{equation}
for some integration constants $c_1, c_2$; therefore
\begin{equation}
k(t) = \frac{c_1 t + c_2 } { \lVert \mathbf{r}_P - \mathbf{r}_T(t)
\rVert} \label{equ:thirteen} .
\end{equation}

This represents the general solution for the optimum form of $k(t)$
which satisfies the specified constraints. Clearly it encompasses
the trivial solution, $k(t)=0 \thickspace \forall \thickspace t$.
Explicit values for the constants depend on the initial conditions,
so it is evident that the solution is highly sensitive to the choice
of starting position and velocity, as is often the case with
variational problems \cite{Lagrangian}. The value of $c_2$ is found
as follows: assuming the initial conditions of pursuer, target and
fixed point are known. We allow $t_0 = 0$, then $k_0 = k(t_0) =
k(0)$ is known. By substituting into \ref{equ:thirteen}, we solve
for $c_2$,
\begin{equation}
c_2 = k_0 ( \lVert \mathbf{r}_P - \mathbf{r}_T(0) \rVert)
\label{equ:fourteen}.
\end{equation}
For an engagement that ends in an interception, $c_1$ can be
similarly found from the desired terminal conditions, a procedure
outlined later. However for an open-ended interaction, a suitable
value for the constant $c_1$ can still be established from the
first-order initial conditions. Differentiating (\ref{equ:twelve})
gives us
\begin{equation}
\dot{k} = \frac{c_1}{\lVert \mathbf{r}_P - \mathbf{r}_T \rVert} + k
\frac{\dot{\mathbf{r}}_T^\prime (\mathbf{r}_P -
\mathbf{r_T})}{\lVert \mathbf{r}_P - \mathbf{r}_T \rVert^2 }
\end{equation}
therefore by defining the initial condition $\dot{k}_0$, we obtain
\begin{equation}
c_1 = \dot{k}_0 (\lVert \mathbf{r}_P - \mathbf{r}_T(t_0) \rVert) -
k_0 \frac{\dot{\mathbf{r}}_T(t_0)^\prime (\mathbf{r}_P -
\mathbf{r}_T(t_0))}{\lVert \mathbf{r}_P - \mathbf{r}_T (t_0)\rVert }
\nonumber .
\end{equation}

A positive value of $\dot{k}_0$ generates a trajectory with a
pursuit characteristic, a negative value gives an escape path.
Different engagements are illustrated below. Figure \ref{fig:lin1}
shows an example  involving a constant-velocity target. A positive
value is used for $k$, which results in a pursuit scenario. Figure
\ref{fig:linesc} shows a trajectory with the same starting
conditions, but in which k is negative, so that the shadower escapes
from the shadowee.

\begin{figure}[ht!]
\begin{center}
\subfigure[Linear interaction, $k > 0: k_0 = 0.1, \dot{k}_0 = 0.2$]{
\label{fig:lin1}
\includegraphics[width=6cm]{lin_k_3D}}
\hspace{.3in} \subfigure[Linear interaction, $k < 0:  k > 0, k_0 =
0.1, \dot{k}_0 = -0.2$]{ \label{fig:linesc}
\includegraphics[width=6cm]{lin_betwee_k}}
\caption{Optimal solutions to linear trajectories}
\end{center}
\end{figure}

To demonstrate the energy efficiency of these paths, we consider two
agents with the same starting position and velocity, camouflaging
themselves against a shadowee moving along a prescribed straight
trajectory. One agent uses the low-energy path as derived above,
while the other moves in a straight line to the interception point
(whilst still maintaining camouflage). Figure \ref{fig:energy} shows
the paths taken. (For simplicity, we look at only two dimensions in
this instance).

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=6cm]{straightline}
\caption{Comparison between a straight interception trajectory and
an energy optimal trajectory. Initial conditions, in cm, are as follows: $X_T(0) =
[30,60], V_T (0) = [650,-20], X_D(0) = [300,-650], V_D(0) = [9,11]$}
\label{fig:energy}
\end{center}
\end{figure}

The initial velocity vector of the straight line path was set to
point in the approximate direction of the interception point of the
optimal trajectory, as to enable a meaningful comparison. The
forward velocity of both pursuers at the beginning of the
interaction is 14 cm/s. The final speed required for the straight
trajectory to still be camouflaged at the interception point is
$1.14 \times 10^3$ cm/s, whereas that required for the optimal
energy path is very much lower,  187.8 cm/s. Given these initial
conditions, then, to pursue a target along a straight line while
remaining camouflaged, a shadower must expend more than 40 times the
energy that would be required by a low-energy pursuit curve.

As alluded to previously, if it is desired to intercept the shadower
within a predetermined time (a so-called 'finite horizon' capture),
or indeed if another geometric condition is to be met, then we can
determine the necessary constant $c_1$ from the end boundary
conditions. In the case of capture in some finite time $t_f$, we say
$k(t_f)=1$, so substituting this condition and equation
\ref{equ:fourteen} into equation \ref{equ:thirteen}, we can write:
\begin{equation}
c_1 = \frac{1}{t_f} \left[ \lVert \mathbf{r}_P - \mathbf{r}_T
(t_f)\rVert - k_0 \lVert \mathbf{r}_P - \mathbf{r}_T(t_0) \rVert
\right] \label{equ:intercept} .
\end{equation}
Figure \ref{fig:lincap}
demonstrates a finite horizon capture path.

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=6cm]{linear_capture}
\caption{Capture trajectory for a shadower with initial conditions
$k_0 = 0.1$, $\dot{k}_0 = 0.2$, static point at $\mathbf{r}_P =
[200, -650, 500]$. Shadowee initial conditions $\mathbf{r}_T(0) =
[30, 60, 150]$, constant velocity $\dot{\mathbf{r}_T} = [200, -20,
60]$. Capture horizon is 12s (CCLs shown here every 0.4s).}
\label{fig:lincap}
\end{center}
\end{figure}

A similar method can be used to find a trajectory for camouflage at
infinity against a target moving at constant velocity. Recall equation
\ref{equ:twentytwo}. We can again find the constants $c_1$ and $c_2$
from the initial position and velocity conditions. Alternatively, for a
capture trajectory, we can determine the optimal $c_1$ for a given
final time from the terminal boundary conditions, so
\begin{equation}
c_1 = \frac{1}{t_f} \left( k(t_f) \mathbf{e}^T \mathbf{e}
-\mathbf{r}_T ^T(t_f) \mathbf{e} - c_2 \right) \label{equ:twentysix} .
\end{equation}

For a capture trajectory, $k(t_f) = 0$, and this is demonstrated in
Figure \ref{fig:infcap}.
For tracking at a constant distance $d = \lVert \mathbf{r}_{T_0}
-\mathbf{r}_{D_0} \rVert = \lVert \mathbf{e} \rVert$, we set $k(t_0)
= k(t) = k(t_f)=1$. An example of the latter tracking result can be
seen in Figure \ref{fig:inftrack}.

\begin{figure}[ht!]
\begin{center}
\includegraphics[width=6cm]{inf_capture}
\caption{Capture using camouflage at infinity. Initial conditions
and velocity of the shadowee are $\mathbf{r}_T(t_0)=[-30 150 150],
\mathbf{v}_T(t_0) = [200, -20, 60]$. Starting point of shadower is
at $[0,0,0]$.} \label{fig:infcap}
\end{center}
\end{figure}

\begin{figure}[ht!]
\begin{center}
\includegraphics[width=6cm]{k_tracking}
\caption{Tracking at a constant distance. Initial conditions and
velocity of the shadowee are identical to Figure \ref{fig:lincap}.
Starting point of shadower is at $[0,0,0]$.} \label{fig:inftrack}
\end{center}
\end{figure}

\subsection{Camouflaging against a target following a quasi-3D
guidance law} \label{sec:quasi3d} In {\em conspecific} two-body
guidance, it may be surmised that both participants have similar
capabilities and are using similar guidance techniques. In such a
scenario, it is unlikely that one participant will maintain a
constant linear (or angular) velocity while the other does not, so
the conditions on target dynamics assumed in the previous examples
may not be useful. However in a conspecific situation, we may be
able to use the similarity of the participants to come up with some
other constraint on the target motion. One such example follows
here.

Recall that our main result in equation \ref{equ:main} shows that
the pursuer's acceleration under Lagrangian camouflage conditions
will be orthogonal to the line-of-sight vector between pursuer and
target. An interaction of this nature will produce a relative motion
vector that lies in a plane. Bodies with trajectories satisfying
this condition are said to be moving in a 'quasi-3dimensional'
manner \cite{yang}. Certain commonly used guidance laws which result
in quasi-3D motion have as their defining characteristic a relative
acceleration of zero along the radial axis between shadowee and
shadower, as does motion camouflage. We examine a situation where the
shadower, $D$, is following a motion camouflaged path, and the shadowee, $T$, is
following a quasi-3D guidance law - in other words, the shadower and
shadowee are using similar (but possibly non-identical) guidance
strategies, both accelerating in a direction orthogonal to the
line-of-sight. Using this information, we can make a general
statement about the function $k(t)$ under these conditions.

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=8cm]{3Dpolar_mc}
\caption{Geometry of motion camouflage in three dimensions in a
spherical reference frame, with origin at the static point. }
\label{fig:3dpolar}
\end{center}
\end{figure}

We examine a camouflaged engagement in a spherical
reference frame (Figure \ref{fig:3dpolar}). The origin is fixed at the static point of the
engagement, and the co-ordinates of the pursuer and target can be
written $(r_D, \theta_D, \phi_D)$ and $(r_T, \theta_T, \phi_T)$
respectively. It is straightforward to show that under motion
camouflage conditions, $\theta_D = \theta_T = \theta$, $\phi_D =
\phi_T = \phi$. Hence we can define an orthogonal set of unit
vectors $(\mathbf{e}_r, \mathbf{e}_\theta, \mathbf{e}_\phi)$ along
the co-ordinate axes, as in Figure \ref{fig:3dpolar}.

The displacement and velocity of the pursuer in this reference frame
can be written
\begin{eqnarray}
\mathbf{r}_D &=& r_D \mathbf{e}_r \nonumber \\
\dot{\mathbf{r}}_D &=& \dot{r}_D \mathbf{e}_r + r_D \dot{\theta}
\cos\phi\mathbf{e}_\theta + r_D \dot{\phi} \mathbf{e}_\phi
\end{eqnarray}
hence the acceleration components along the co-ordinate axes are
\begin{subequations}
\begin{align}
a_{D_r} &= \ddot{r}_D - r_D \dot{\phi}^2 - r_D\dot{\theta}^2
\cos^2\phi \\
a_{D_\theta} &= r_D \ddot{\theta} \cos\phi +
2\dot{r}_D\dot{\theta}\cos\phi - 2 r_D
\dot{\phi}\dot{\theta}\sin\phi \\
a_{D_\phi} &= r_D \ddot{\phi} + 2 \dot{r}_D \dot{\phi} + r_D
\dot{\theta}^2 \cos\phi \sin\phi .
\end{align}
\end{subequations}
According to equation (\ref{equ:main}), the acceleration of the
pursuer $D$ is entirely orthogonal to the line-of-sight vector
$\mathbf{e}_r$, or in other words, the radial component of the
acceleration is zero. Hence we can write
\begin{equation}
\ddot{r}_D - r_D(\dot{\theta}^2 \cos^2\phi + \dot{\phi}^2) = 0
\nonumber .
\end{equation}
Applying equation (\ref{equ:first}), we establish the following
condition for $k(t)$:
\begin{equation}
\frac{d^2}{dt^2}(k r_T) = r_T (\dot{\theta}^2\cos^2\phi +
\dot{\phi}^2) \label{equ:angv} .
\end{equation}
The angular velocity of $D$ is found in the following way:
\begin{equation}
\mathbf{\Omega} = \frac{\mathbf{r}_D \times
\dot{\mathbf{r}}_D}{r_D^2} = -\dot{\phi} \mathbf{e}_\theta +
\dot{\theta}\cos\phi \mathbf{e}_\phi,
\end{equation}
hence we can replace (\ref{equ:angv}) with the following general
equation:
\begin{equation}
\frac{d^2}{dt^2}(k r_T) = r_T \Omega^2 \label{equ:omega}.
\end{equation}

Let $\mathbf{r} = \mathbf{r}_T - \mathbf{r}_D$. If the shadowee is
using a quasi-3D guidance law to react to the shadower, then the
following holds true \cite{yang}:
\begin{equation}
\frac{d^2}{dt^2}{r} = r \Omega^2 \label{equ:omegafund}
\end{equation}
We can write the left-hand side of this equation in terms of $r_T,
k$:
\begin{eqnarray}
\ddot{r} &=& \frac{d^2}{dt^2}(r_T (1-k)) \nonumber \\
&=& \ddot{r_T} - (\ddot{k}r_T + 2\dot{k}\dot{r}_T + k \ddot{r}_T)
\nonumber \\
&=& \frac{d^2}{dt^2}(r_T) - \frac{d^2}{dt^2}(k r_T) .
\end{eqnarray}

Doing the same to the right-hand side, we find
\begin{equation}
\frac{d^2}{dt^2}(r_T) - \frac{d^2}{dt^2}(k r_T) = r_T \Omega^2 - (k
r_T) \Omega^2 \label{equ:omega2}.
\end{equation}
Recall the general equation described in (\ref{equ:omega}). We can
rearrange this to find a differential equation in $k,r_T$ to
describe $\Omega$:
\begin{equation}
\Omega^2 = \frac{1}{k r_T} \frac{d^2}{dt^2}(k r_T)
\end{equation}
Substituting into (\ref{equ:omega2}) and expanding, we find that $k$
satisfies the following differential equation: \begin{equation}
\ddot{k} r_T + 2\dot{k}\dot{r}_T = 0 \nonumber
\end{equation}
which has a solution
\begin{equation}
k(t) = c_1 + c_2 \int_{t_0}^{t} \frac{1}{r_T(t)^2} dt
\label{equ:quasi3D} .
\end{equation}

The exact form of $k(t)$ and the constants $c_1, c_2$ depend on the
precise formulation of the guidance law being used by the shadowee
and the initial conditions of the engagement. An example of two-body guidance using a
specific quasi-3D guidance law is given in section \ref{sec:pn}.

\section{Possible Applications} \label{sec:app}
In order to demonstrate a possible use for these optimal path
equations, we consider what kind of guidance system may be easily
modified to produce trajectories which satisfy the above conditions.
A common tracking strategy which has been observed in insects
such as blowflies and houseflies \cite{Boeddeker03}, \cite{Land2}, is for the pursuer to
apply an acceleration proportional to the relative angular velocity
between the pursuer and target. This type of guidance is conventionally
known as proportional navigation (PN), and as well as being observed in nature,
has been used for many years in autonomous and independently guided tracking
systems. Motion camouflage is a natural candidate for a
modified PN guidance law \cite{Krishna1},
since the relative angular position is a
key variable when it comes to defining and controlling for motion
camouflage.

Consider the problem of static point motion camouflage in two
dimensions. We use a polar reference frame, as in section
\ref{sec:quasi3d}, however for simplicity we will restrict ourselves
to two dimensions. This co-ordinate system can be described by
$(\mathbf{e}_r, \mathbf{e}_\theta)$, where $\mathbf{e}_r$ is a unit
vector along the line-of-sight (LOS) between agents $D$ and $T$, and
$\mathbf{e}_\theta$ is a unit vector orthogonal to $\mathbf{e}_r$.

Given equations (\ref{equ:omegafund}) and (\ref{equ:main}) we can
write the acceleration of the shadower D as
\begin{equation}
a_D = a_{D_\theta} = (k r_T) \ddot{\theta} + 2\frac{d}{dt} (k r_T)
\dot{\theta} \nonumber.
\end{equation}
It is straightforward to see that the above is equivalent to
\begin{equation}
a_D = k a_T + 2\dot{k} r_T \dot{\theta} \label{equ:mcpn_fund}.
\end{equation}
This is a form of augmented PN guidance, which we term MCPN, and depending on the value
of $a_T$, this augmented equation may reduce further to a simple PN function. For example,
if the shadowee is moving with a constant velocity, we can write equation
(\ref{equ:mcpn_fund}) in terms of the relative distance and line of
sight velocity,
\begin{eqnarray}
a_D &=& 2 \frac{\dot{k} r}{1-k} \dot{\theta} \nonumber \\
&=& \Gamma r \dot{\theta} \label{equ:PNconst}
\end{eqnarray}
where $\Gamma$ is a variable gain function depending on the ratio
($k$) of the distances of the shadower and shadowee from the static
point.

\subsection{MCPN Guidance against a target moving at constant velocity}
We assume an oblivious target moving at constant velocity. The relevant guidance  law is
described in equation \ref{equ:PNconst}.
Figure \ref{fig:PNMC_accel} shows the camouflage path achieved using
a PN-guided pursuer following a motion camouflaged path under locally
energy-minimal conditions (MCPN), and the radial
and angular acceleration required.

\begin{figure}[ht!]
\begin{center}
\subfigure[Shadower and shadowee trajectory, given initial conditions:
$\dot{k}_0 = 0.2$, $k_0 = 0.1$, $\mathbf{r}_T(0) = (30, 60)$,
$\dot{\mathbf{r}}_T(0) = (200, -20)$, $\mathbf{r}_P = (200,
-650)$]{\label{fig:PNMC_nm}
\includegraphics[width=6cm]{2D_kPN}}
\hspace{.3in}\subfigure[Acceleration commands in the
spherical frame $(A_r \mathbf{e}_r, A_t \mathbf{e}_{\theta})$]{\label{fig:PNMC_accel}
\includegraphics[width=6cm]{2D_kPN_accel}}
\caption{Motion Camouflage path for a non-maneuvering target using
PN-derived acceleration commands. Note that in figure (b), $A_r = 0$, as expected.}
\end{center}
\end{figure}

\subsection{MCPN guidance against a reactive guided target} \label{sec:pn}
Previously (\S \ref{sec:quasi3d}) we discussed a
conspecific pursuit scenario. There, we derived a motion camouflage
equation that may be used against
a reactive shadowee which is simultaneously tracking the shadower.
This may possibly be of use to robotics researchers or autonomous agents
- it will almost certainly give us some insight into the flight
patterns seen in insects known to use motion camouflage. Hence we
now develop a guidance law that may be used to maintain camouflage
against a similarly capable manoeuvering target, provided that
some rudimentary facts about the target dynamics are known.

Suppose the shadowee $T$ has a non-constant velocity, and in fact is
also tracking the pursuer, using a known guidance law. Let the
shadowee be using a quasi-3D proportional guidance law known as True
Proportional Navigation (TPN), which takes the form
\begin{equation}
a_T = \lambda \dot{r}_0 \dot{\theta} \label{equ:GTPN} .
\end{equation}
In this formulation, $\lambda$ is a gain constant, $\dot{r}_0$ is the
initial range between the shadower and shadowee,
and $\theta$ is the line-of-sight vector between shadower and shadowee (from the shadowee's perspective).

Recall that according to Yang and Yang \cite{yang}, with a quasi-3D
guidance law, the relative radial acceleration $a_{R_r} = 0$. From
(\ref{equ:main}) we know $a_{D_r} = 0$, hence we can state that
$a_{T_r} = 0$. Therefore for a shadowee using TPN against a motion
camouflaged shadower, the following two equations hold:
\begin{subequations}\label{equ:yang1}
\begin{align}
\ddot{r}_T &= r_T \dot{\theta}^2 \label{equ:at1}\\
a_T &= r_T \ddot{\theta} + 2 \dot{r}_T \dot{\theta} = \lambda
\dot{r}_0 \dot{\theta}  \label{equ:at2}
\end{align}
\end{subequations}

We make the following variable substitution \cite{yang}: let $V_r =
\dot{r}_T$, $V_\theta = r_T \dot{\theta}$, then the equations in
(\ref{equ:yang1}) become
\begin{subequations}\label{equ:yang2}
\begin{align}
\dot{V}_r - V_\theta \dot{\theta} &= 0 \label{equ:at3} \\
\dot{V}_\theta + V_r \dot{\theta} &= \lambda \dot{r}_0 \dot{\theta}
\end{align}
\end{subequations}

We can change the independent variable $t$ to $\theta$ and solve the
above to find
\begin{eqnarray}
V_r &=& A \cos(\theta + B) + \lambda \dot{r}_0 \\
V_\theta &=& -A \sin(\theta + B) \label{equ:at4}
\end{eqnarray}
where $A, B$ are constants (which can be found from initial
conditions). From (\ref{equ:at4}) and (\ref{equ:quasi3D}), $k(t)$
takes the following form:
\begin{eqnarray}
k(t) &=& c_2 + c_1 \int_{t_0}^{t} \frac{-\dot{\theta}^2}{A^2
\sin^2(\theta + B)} dt \\
B &=& \arctan\left(\frac{r_{T_0} \dot{\theta}_0}{\lambda \dot{r}_0 -
\dot{r}_{T_0}} \right) + \theta_0 \nonumber \\
A &=& \frac{\dot{r}_{T_0} - \lambda\dot{r}_0}{\cos(\theta_0 + B)}
\end{eqnarray}
which can be solved numerically. The shadower acceleration can be
written
\begin{equation}
a_D = (\lambda k \dot{r}_0 + 2 r \frac{\dot{k}}{1-k}) \dot{\theta} =
\Gamma^* \dot{\theta},
\end{equation}
which again gives us a PN guidance law, this time with variable gain
$\Gamma^*$. A guided shadower using a low-energy path derived with
the above method against a guided target can be seen in Figure
\ref{fig:MCPNvsPN}, and the desired accelerations of both target and
pursuer are shown in Figure \ref{fig:MCPNvsPNaccel}.

\begin{figure}[ht!]
\begin{center}
\subfigure[The shadowee path is labelled 'TPN law', the shadower's path is labelled 'MCPN'.
Initial conditions are: $\mathbf{r}_P = (2000 -1650)$,
$\mathbf{r}_T(0) = (30,60)$, $\dot{\mathbf{r}}_T(0)=(200,-20)$
.]{\label{fig:MCPNvsPN}
\includegraphics[width=6cm]{PNvsMCPN}}
\hspace{.3in}\subfigure[Acceleration commands in the respective
body-centred spherical frame for both shadowee (TPN) and shadower
(MCPN)]{\label{fig:MCPNvsPNaccel}
\includegraphics[width=6cm]{PNvsMCPN_accel}}
\caption{MCPN path against an active target using TPN guidance. (a)
Pursuer and target trajectory, given $\dot{k}_0 = 0.08$, $k_0 = 0.1$
(b) Acceleration commands in the spherical frame for both pursuer
and target $(A_r \mathbf{e}_r, A_t \mathbf{e}_{\theta})$. For both
bodies, the radial acceleration is zero. As the endgame approaches,
the acceleration of both shadowee and shadower increases, but over
the course of the interaction the acceleration of the MCPN body is
notably less than that of the TPN body.}
\end{center}
\end{figure}

It is hoped that by finding elegant and efficient means of mimicking
pursuits and interactions observed in nature, we can gain insight
into the guidance mechanisms used by insects and other animals. For
example, research by Boeddeker, et al \cite{Boeddeker03}, and Land,
et al \cite{Land2}, has found that insect pursuit systems can be
modelled quite simply using a static first-order gain controller
with only a few input variables readily available via the visual
system. Similarly, Ghose, et al \cite{Ghose}, show evidence that
bats use an interception strategy commonly found in guided missiles
to intercept prey. By combining these simple models with a guidance
system that enables us to replicate gross characteristics of known
flights, we can obtain a streamlined but fully controllable
navigational system.

\section{Conclusion}
This study describes how energy-efficient strategies can be derived
for tracking or shadowing moving objects whilst maintaining motion
camouflage. A series of control strategies is presented for
implementing energy-efficient motion camouflage under various
conditions. The findings can be usefully applied to a variety of
tracking situations, as well as provide insights into some of the
behaviours exhibited by insects and animals. Our most important result was
the discovery of a necessary orthogonal condition to the pursuer acceleration
under an energy-optimal motion camouflage path.

This work was funded by an ANU Postgraduate Scholarship (to N.C.)
and had partial support from the ARC Centre of Excellence in Vision
Science (to M.S.). The authors would like to thank Jochen Zeil for
discussion and advice and Alan Carey for an illuminating
conversation.

config: arxiv


TITLE: Put x in terms of u and v
QUESTION [0 upvotes]: I have these two equations
$$u = \frac{2x}{x^2 + y^2} \\
v = \frac{-2y}{x^2 + y^2}$$
And I need to put $x$ in terms of $u$ and $v$. If I take polar co-ordinates and plug them in I get(in the case of $u$), because
(rcos(theta))^2 + (rsin(theta))^2 = 1
$$u = 2r\cos(\theta)$$
Can I simply change that back to
$$u = 2x$$
?

REPLY [1 votes]: Let $x = r \cos \theta$ and $y = r \sin \theta$. Then
$$
u = \frac{2x}{x^2 + y^2} = \frac{2 \cos \theta}{r}
$$
$$
v = \frac{-2y}{x^2 + y^2} = \frac{- 2 \sin \theta}{r}
$$
Dividing these gives
$$
\tan \theta = - \frac{v}{u} \Rightarrow \theta = \tan^{-1} \left(-\frac{v}{u}\right),
$$
and squaring and then adding gives
$$
u^2 + v^2 = \frac{4}{r^2} \Rightarrow r = \frac{2}{\sqrt{u^2+v^2}}.
$$
You now have $r$ and $\theta$, and thus $x$ and $y$, in terms of $u$ and $v$.

REPLY [1 votes]: In polar/Cartesian coordinates, using standard variables, $x^2+y^2 = r^2$, so your first equation could be written $$u=\frac{2x}{r^2}$$ But then also, $x=r\cos\theta$, so $$u=\frac{2\cos(\theta)}{r}$$
So there is your mistake.

REPLY [0 votes]: Using polar coordinates:
$$u=\frac{2x}{x^2+y^2}\longrightarrow\frac{2r\cos\theta}{r^2}=\frac{2\cos\theta}{r}$$
$$v=-\frac{2y}{x^2+y^2}\longrightarrow -\frac{2r\sin\theta}{r^2}=-\frac{2\sin\theta}{r}$$
which is different from what you wrote...


TITLE: Fractional Sobolev spaces and extension by zero
QUESTION [3 upvotes]: The all-wise Wikipedia suggest (https://en.wikipedia.org/wiki/Sobolev_space#Extension_by_zero) that for $s > 1/2$ any function from $H^s_0(\Omega)$ can be extended by zero
to whole $\mathbb{R}^n$ (with the extension being in $H^s(\mathbb{R}^n)$)
under some mysterious condition, namely $s \neq \mbox{integer} + 1/2$.
I saw this proposition in a couple of papers, but always without a proof or
reference.
Does anyone has an idea where it comes from?
Thank you in advance

REPLY [2 votes]: The answer is blowin' in the wind... unless $\Omega$ is Lipschitz domain, in which case the proof can be found in the book of`W. McLean  "Strongly Elliptic Systems and Boundary Integral Equations".
I would also recommend the paper "Traces, extensions and co-normal derivatives for elliptic systems on Lipschitz domains" by Sergey Mikhailov which is available in the net and has well documented references.
Good luck everyone!


TITLE: What does it mean to say "almost always" ?
QUESTION [1 upvotes]: I have a set, $A$, of $m \times n$ matrices with certain properties and a subset $B$ of $A$. I would like to say that when randomly selecting such a matrix, I am "almost always" never in $B$. I can show that $A$ is the disjoint union of subsets, $A_j$, such that for each $A_j$, the measure of $A_j\cap B$ is 0. However, this union is uncountable. Is this enough to reasonably conclude that my randomly selected matrix will "almost always" never be in $B$?
Thanks for the help!
Best,
Julie
Additional info: Each $A_j$ has the following properties :

the interior of $A_j$ is a nonempty open subset of $\mathbb{R}^{m\times n}$
$\partial A_j = A_j\cap B$.

REPLY [1 votes]: I see some contradiction in your hypotheses: since the $A_j$'s are disjoint and have non empty interiors, the union should be at most countable (there can't exist more $A_j$'s than the cardinal of the set of rational points in $\mathbb{R}^{m\times n}$).


text:
\begin{document}

\title{Lattice stick number of spatial graphs}

\author[H. Yoo]{Hyungkee Yoo}
\address{Department of Mathematics, Korea University, Seoul 02841, Korea}
\email{lpyhk727@korea.ac.kr}
\author[C. Lee]{Chaeryn Lee}
\address{Department of Mathematics, University of Illinois Urbana Champaign, Urbana, IL 61801}
\email{chaeryn2@illinois.edu}
\author[S. Oh]{Seungsang Oh}
\address{Department of Mathematics, Korea University, Seoul 02841, Korea}
\email{seungsang@korea.ac.kr}

\keywords{graph, lattice stick number, upper bound}
\thanks{Mathematics Subject Classification 2010: 57M25, 57M27}
\thanks{The corresponding author(Seungsang Oh) was supported by the National Research Foundation of Korea(NRF) grant funded by the Korea government(MSIP) (No. NRF-2017R1A2B2007216).}

\maketitle

\begin{abstract}
The lattice stick number of knots is defined to be the minimal number of straight sticks in the cubic lattice
required to construct a lattice stick presentation of the knot.
We similarly define the lattice stick number~$s_{L}(G)$ of spatial graphs $G$
with vertices of degree at most six (necessary for embedding into the cubic lattice),
and present an upper bound in terms of the crossing number~$c(G)$
$$ s_{L}(G) \leq 3c(G)+6e-4v-2s+3b+k, $$
where $G$ has $e$~edges, $v$~vertices, $s$~cut-components, $b$~bouquet cut-components,
and $k$~knot components.
\end{abstract}

\section{Introduction} \label{sec:intro}
All definitions and statements throughout this paper will concern the piecewise linear category.
A graph consists of vertices connected by edges allowing loops and multiple edges.
A spatial graph is an embedding of a graph into $\mathbb{R}^3$.
Two spatial graphs are considered the same if there exists an ambient isotopy taking one to the other.

An interesting question involving spatial graphs may ask
how we can make a given spatial graph out of straight sticks.
A stick presentation of a spatial graph consists of straight sticks glued together end to end.
The minimal number of sticks necessary to construct a stick presentation of a spatial graph $G$ is
defined as the {\em stick number} $s(G)$ of $G$.
Specially, we may choose to use sticks in the cubic lattice $\mathbb{Z}^3$.
A spatial graph embedded into $\mathbb{Z}^{3}$ is called its lattice stick presentation.
The length of each stick is a positive integer.
The {\em lattice stick number\/} $s_{L} (G)$ of $G$ is the minimal number of sticks necessary to construct
a lattice stick presentation of $G$.
See Figure~\ref{fig:latticestick} for an example of a stick and lattice stick presentation of
the $\theta$-curve $3_1$.

\begin{figure}[h]
\includegraphics{fig1.eps}
\caption{Stick and lattice stick presentation}
\label{fig:latticestick}
\end{figure}

Much research has been made on the stick number and lattice stick number of knots and links.
As for the stick number of knots,
Randell~\cite{R} proved that $s(3_1)=6$, $s(4_1)=7$, $s(K)=8$ for all prime knots with five or six crossings
and $s(K) \geq 8$ for other nontrivial knots $K$.
The stick number of a $(p, q)$-torus knot with $p < q < 2p$ was shown to be $2q$ by Jin~\cite{Ji}.
Adams et al.~\cite{ACCJSZ} independently found the stick number of all $(n, n \! + \! 1)$-torus knots
and their compositions.
Negami~\cite{Ne} found bounds on the stick number for nontrivial knots $K$
with respect to the crossing number $c(K)$ which is $\frac{5+ \sqrt{25+8(c(K)-2)}}{2} \leq s(K) \leq 2c(K)$.
The upper bound was improved by Huh and Oh~\cite{HO3} to $s(K) \leq \frac{3}{2} c(K)+\frac{3}{2}$.
McCabe~\cite{Mc} proved that $s(K) \leq c(K) +3$ for a $2$-bridge knot or link $K$
except the unlink and the Hopf link.
Huh, No and Oh~\cite{HNO} reduced this bound by 1 for a $2$-bridge knot or link $K$ with $c(K) \geq 6$.
The lower bound was improved by Calvo~\cite{Ca} to $\frac{7 + \sqrt{1+8c(K)}}{2} \leq s(K)$.

There are also various results concerning the lattice stick number of knots and links.
It was proved by Diao~\cite{Di} that $s_{L}(3_1) = 12$.
Huh and Oh~\cite{HO1, HO2} showed that $s_{L}(4_1) = 14$ and
that all other nontrivial knots have lattice stick number at least 15.
Adams et al.~\cite{ACCJSZ} found that $s_{L}(T_{p,p+1}) = 6p$ for $p \geq 2$ where $T_{p,p+1}$ is
a $(p, p + 1)$-torus knot.
All links with more than one component with lattice stick number at most 14
were found by Hong, No and Oh~\cite{HNO2}.
Janse Van Rensburg and Promislow~\cite{JaP} proved that $s_{L}(K) \geq 12$ for nontrivial knots $K$.
Adams et al.~\cite{ACCJSZ} found an upper bound $s_{L}(K) \leq 6c(K)-4$.
An improved upper bound $s_{L}(K) \leq 3c(K)+2$ was found by Hong, No and Oh~\cite{HNO1}
using the arc presentation of $K$.

We extend the study of the stick number and lattice stick number of knots to spatial graphs.
Lee, No and Oh~\cite{LNO2} found an upper bound of the stick number of spatial graphs $G$ which is
$s(G) \leq \frac{3}{2} c(G) + 2e - \frac{v}{2} + \frac{3b}{2}$
where $e$, $v$ and $b$ are the number of edges, vertices and bouquet cut-components, respectively.
The notion of bouquet cut-components will be explained just before the main theorem.

In this paper, we find an upper bound of the lattice stick number of spatial graphs.
We only consider spatial graphs which have vertices of degree at most six,
due to the structure of the cubic lattice $\mathbb{Z}^3$.
Following convention, we assume that a spatial graph $G$ does not have vertices of degree one or two,
except when it has a disjoint circle component, called a {\em knot component\/}.
We say that a knot component consists of a vertex and an edge.

\begin{figure}[h]
\includegraphics{fig2.eps}
\caption{Knot component and bouquet  cut-component}
\label{fig:bouquet}
\end{figure}

We consider two types of 2-spheres that separate $G$ into two parts.
Such a 2-sphere is called a {\em splitting-sphere\/} if it does not meet $G$,
and a {\em cut-sphere\/} if it intersects $G$ in a single vertex,
which is called a {\em cut-vertex\/}.
We maximally decompose $G$ into {\em cut-components\/} by cutting $G$
along a maximal set $\mathcal{S}$ of splitting-spheres and cut-spheres
where any two spheres are either disjoint or intersect each other in a cut-vertex.
A cut-component of $G$ is called a {\em bouquet  cut-component\/} if it consists of one vertex and loops.
See Figure~\ref{fig:bouquet}.
Let ${\rm d}(x)$ denote the degree of a vertex $x$ of $G$.

\begin{theorem} \label{thm:bound}
Let $G$ be a spatial graph with  $3 \leq {\rm d}(x) \leq 6$ for each vertex $x$,
only allowing ${\rm d}(x) \! = \! 2$ for the unique vertex of each knot component.
If $G$ has $e$ edges, $v$ vertices, $s$ cut-components, $b$ bouquet cut-components
and $k$ knot components, then
$$ s_{L}(G) \leq 3c(G)+6e-4v-2s+3b+k. $$
\end{theorem}

It is noteworthy that for a knot $K$ this result implies $s_{L}(K) \leq 3c(K)+4$
which is close to the known upper bound $s_{L}(K) \leq 3c(K)+2$ in~\cite{HNO1}.

\section{Arc index of spatial graphs} \label{sec:arc}

There is an open book decomposition of $\mathbb{R}^3$ that has open
half-planes as pages and the standard $z$-axis as the binding axis.
We embed a spatial graph $G$ into an open book with finitely many pages
so that it meets each page in exactly one simple arc with two different end-points on the binding axis.
Therefore the binding axis contains all vertices of $G$ and
finitely many points from the interiors of the edges of $G$
and each edge of $G$ may pass from one page to another across the binding axis.
The realization of an arc presentation of this type for a spatial graph is introduced in~\cite{LNO1}.
An arc presentation of the $\theta$-curve $3_1$ with six pages is depicted in Figure~\ref{fig:arc}.
The {\em arc index\/} $\alpha(G)$ is defined to be the minimal number of
pages among all possible arc presentations of $G$.

\begin{figure}[h]
\includegraphics{fig3.eps}
\caption{Arc presentation}
\label{fig:arc}
\end{figure}

In an arc presentation of $G$,
we turn the pages so that they are all positioned to the right of the binding axis
and assign natural numbers $1, 2, \dots, \alpha(G)$ to all arcs from back to front
which are called the page numbers.
The points of $G$ on the binding axis are called the binding points.

\begin{lemma} \label{lem:binding}
Suppose that $G$ has $v$ vertices and $e$ edges.
If $\beta$ is the number of binding points of an arc presentation of $G$ with $\alpha(G)$ arcs then
$$ \beta = \alpha(G) +v -e.$$
\end{lemma}

\begin{proof}
Given an arc presentation of G with $\alpha(G)$ arcs, let us count the number of endpoints of all the arcs.
Note that each of the $\beta \! - \! v$ binding points which does not correspond to vertices of $G$ has degree 2.
$$ 2\alpha(G)=2(\beta-v)+\sum_{x \in V} {\rm d}(x), $$
where $V$ is the set of vertices of $G$.
Since $\sum_{x \in V}{\rm d}(x)=2e$, we have the desired equality.
\end{proof}

Bae and Park~\cite{BP} found an upper bound on the arc index of a nontrivial knot
in terms of the crossing number.
Lee, No and Oh generalized the argument used in Bae and Park's paper
to find an upper bound on the arc index of a spatial graph as follows.
This bound is crucial in the last part of the proof of the main theorem.

\begin{theorem} {\textup{(Lee-No-Oh~\cite{LNO1})}} \label{thm:LNO1}
Let $G$ be any spatial graph with $e$ edges and $b$ bouquet cut-components.
Then
$$ \alpha(G) \leq c(G)+e+b. $$
\end{theorem}

\section{Lattice presentation} \label{sec:stick}

In this section we prove Theorem~\ref{thm:bound}.
Let $G \! = \! (V,E)$ be a spatial graph with  $3 \leq {\rm d}(x) \leq 6$ for each vertex $x$,
only allowing ${\rm d}(x)=2$ for vertices of knot components.
Recall that each knot component consists of a vertex and an edge.
Suppose that $G$ has $e$ edges, $v$ vertices, $s$ cut-components,
$b$ bouquet cut-components and $k$ knot components.
Let $G=G_1 \cup G_2 \cup \dots \cup G_s$ be the cut-component decomposition of $G$.
Note that $\alpha(G)=\sum \alpha(G_k)$ as mentioned in~\cite[Claim~$2$]{LNO1}.

We may assume that $G$ is non-splittable,
hence no 2-sphere decomposing $G$ is a splitting-sphere.
First we focus on each cut-component.

\subsection{Lattice presentation of a cut-component} \label{subsec:component} \hspace{10mm}

A stick in the cubic lattice $\mathbb{Z}^{3}$ parallel to the $x$-axis is called an $x$-stick.
Each $yz$-plane on which the ends of an $x$-stick are placed is called an $x$-level.
Sticks and levels corresponding to the $y$- and $z$-coordinates are defined analogously.

Given an arc presentation of a spatial graph,
we move the binding axis to the line $y \! = \! x$ on the $xy$-plane
and replace each arc with two connected sticks,
one $x$-stick and one $y$-stick situated properly below the line $y \! = \! x$.
For a better view we slightly perturb some sticks if they overlap.
The result is called a {\em lattice arc diagram\/} of the spatial graph on the plane.
See Figure~\ref{fig:lattice}.

\begin{figure}[h]
\includegraphics{fig4.eps}
\caption{Lattice arc diagram and lattice presentation}
\label{fig:lattice}
\end{figure}

We first construct a lattice presentation $L_k$ of a cut-component $G_k$ of $G$ in $\mathbb{Z}^{3}$.
Let $D_k$ be a lattice arc diagram of $G_k$ in the $xy$-plane with $\alpha(G_k)$ arcs
consisting of $\alpha(G_k)$ $x$-sticks and $\alpha(G_k)$ $y$-sticks.
To begin, place all arcs of $D_k$ on $z$-levels in the order of their page numbers starting from the bottom.
For each set of arcs that share a common binding point,
connect the arcs by adding successive $z$-sticks between the lowest and the highest $z$-levels.

We specially distinguish some classes of cut-components.
A cut-component of $G$ is called an {\em arc cut-component\/}
if it consists of one edge with two distinct end points
and a $\theta_n$ {\em cut-component\/} if it consists of two vertices
and $n$ edges connecting them for $n \geq 2$.
A $\theta_n$ cut-component is called trivial if it can lie on a plane.

We are always able to remove two more sticks from $L_k$ as follows.
Consider the first binding point $b_1$ of $D_k$ where only $x$-sticks are attached.
Focus on the $x$- and $z$-sticks of $L_k$ on the $xz$-plane associated to $b_1$.
One can slide the $z$-sticks in the positive $x$-axis direction on this plane
until the shortest $x$-stick disappears as illustrated in Figure~\ref{fig:sliding}.
This means that we can reduce the number of $x$-sticks by one.
Similarly we repeat this replacement on the last binding point of $D_k$ as well to delete one $y$-stick.
Note that if $G_k$ is a trivial $\theta_n$ cut-component we can delete $n$ $x$-sticks
even though we slide on the $xz$-plane corresponding to binding point $b_1$ only;
if $G_k$ is an arc cut-component, we discuss the matter separately in Section~\ref{subsec:arc}.

\begin{figure}[h]
\includegraphics{fig5.eps}
\caption{Side-sliding}
\label{fig:sliding}
\end{figure}

This replacement is called {\em side-sliding\/}
and the resulting $L_k$ is our desired lattice presentation associated to $G_k$.
The reader must be aware that this lattice presentation $L_k$ is not exactly an embedding of $G_k$
because each vertex of $G_k$ with degree larger than 3 is replaced with
several vertices with degree 3 and connecting edges which are $z$-sticks.
We will adjust this problem in Section~\ref{subsec:merging} by vertex-merging.

\subsection{Combining all cut-components} \label{subsec:comb} \hspace{10mm}

Now we combine all lattice presentations associated to cut-components into one.
Even though there is a unique cut-component decomposition,
sets of decomposing cut-spheres are not unique.
Choose a set $\mathcal{S}$ of decomposing cut-spheres so that
given any two cut-spheres sharing a cut-vertex, one must be contained in the ball bounded by the other.

Since all cut-spheres in $\mathcal{S}$ are partially nested,
we construct a tree structure whose vertices are the cut-components $G_i$'s
and whose edges correspond to the related cut-spheres as in Figure~\ref{fig:tree}.
Re-order the indices of the $G_i$'s so that
$G_1$, as the root of the tree, indicates the cut-component lying in the unbounded region
and the remaining follow the partial order of the tree structure.

\begin{figure}[h]
\includegraphics{fig6.eps}
\caption{Tree structure on the set of cut-components}
\label{fig:tree}
\end{figure}

For each $G_i$, its adjacent cut-components $G_j$ in the tree structure are called
{\em branch cut-components\/} of $G_i$ for $j \! > \! i$, and
{\em stem cut-component\/} otherwise as in Figure~\ref{fig:branch}.
Each cut-component except $G_1$ has a unique stem cut-component.
Furthermore, if two cut-components share a stem cut-component,
they cannot share a cut-vertex
since cut-spheres meeting at a cut-vertex are totally nested.

\begin{figure}[h]
\includegraphics{fig7.eps}
\caption{Branch and stem cut-component}
\label{fig:branch}
\end{figure}

Now we stack up all the constructed lattice presentations $L_k$'s in inductive order with respect to the indices as follows.
First we put $L_1$ on the lowest floor.
After stacking $L_k$'s for $k \! < \! j$,
we connect $L_j$ to its unique stem cut-component $L_i$ ($i \! < \! j$).
There is a set of successive $z$-sticks of $L_i$ related to the cut-vertex of $G$ where $G_i$ and $G_j$ meet.
Let $\overline{p}_i$ be the topmost point of the union of these $z$-sticks.
Similarly let $\underline{p}_j$ be the bottommost point of the union of the successive $z$-sticks
of $L_j$ related to the same cut-vertex.
We take an infinite cylinder for $L_j$ whose core axis runs through $\overline{p}_i$ and is parallel to the $z$-axis.
Assume that the radius of the cylinder is sufficiently small.
Fit $L_j$ into the cylinder so that $\underline{p}_j$ lies on the core of the cylinder and
$L_j$ is positioned above $L_{j-1}$.
Connect the two points $\overline{p}_i$ and $\underline{p}_j$ by a $z$-stick as in Figure~\ref{fig:combing}.
Let $L$ be the lattice presentation obtained by combining all the $L_k$'s.
It is noteworthy that the word ``sufficiently small" requires
the set of constructed cylinders to be partially nested as in the tree structure.

\begin{figure}[h]
\includegraphics{fig8.eps}
\caption{Combining cut-components}
\label{fig:combing}
\end{figure}

\subsection{Vertex-merging} \label{subsec:merging} \hspace{10mm}

In this subsection we adjust this lattice presentation $L$ to be an embedding of $G$.
We only need to consider the arcs that are related to the vertices of $G$ with degree larger than 3.

Let $x$ be a vertex of $G$ with degree $d$ where $4 \leq d \leq 6$.
In the previous construction of $L$, vertex $x$ is replaced by $d \! - \! 2$ vertices with degree 3
as in the left picture depicted in Figure~\ref{fig:merging}.
There are $d \! - \! 1$ successive $z$-sticks and $d$ $x$- or $y$-sticks corresponding to $x$.
Assign $e_i$, $i \! = \! 1,\dots,d$, to these $x$- or $y$-sticks from bottom to top,
and $z_i$ to the endpoint of $e_i$ corresponding to $x$.
In particular, $z_2$ is called the pivot vertex and will eventually indicate the vertex $x$.

\begin{figure}[h]
\includegraphics{fig9.eps}
\caption{Vertex-merging}
\label{fig:merging}
\end{figure}

We start by fixing the sticks $e_1$, $e_2$ and $e_d$.
Now we merge the vertex $z_3$ to the pivot vertex $z_2$ by sliding a small segment of $e_3$ near $z_3$
along the $z$-stick $z'$ connecting $z_2$ and $z_3$ as in Figure~\ref{fig:merging2}.
More precisely, we move this small segment of $e_3$ straight down along the shaded region until it meets $z_2$
and add a $z$-stick parallel to $z'$ connecting the broken endpoints.

There are still other ways to merge $z_3$ to $z_2$;
we slightly translate $e_3$ in one direction perpendicular to $e_3$ on the $xy$-plane.
Similarly, add a small $x$- or $y$-stick and a $z$-stick parallel to $z'$
connecting $z_2$ and the endpoint of $e_3$ near $z_3$.
Obviously the stick attached to the other endpoint of $e_3$ should be shrunk or extended
slightly to be connected to $e_3$.

This procedure is called {\em vertex-merging\/}.
During vertex-merging, vertex $z_3$ with degree 3 disappears,
pivot vertex $z_2$ becomes a vertex with degree 4
and the number of sticks increases by 1.
It is worth noting that there are at least two ways of applying vertex-merging to $z_3$
without newly merged $e_3$ colliding with $e_2$.

\begin{figure}[h]
\includegraphics{fig10.eps}
\caption{Several ways of vertex-merging}
\label{fig:merging2}
\end{figure}

If $d \geq 5$, we similarly repeat vertex-merging on $z_4$
since there is still at least one way of applying vertex-merging to $z_4$ avoiding $e_2$
and the direction occupied by newly merged $e_3$ near $z_2$.

For $d=6$, there is a unique direction $\vec{v}$ which is not occupied by
$e_2$, newly merged $e_3$ nor $e_4$.
If the direction of $e_5$ is not opposite to $\vec{v}$,
then we perform vertex-merging on $z_5$ in the direction $\vec{v}$
as in the upper right picture in Figure~\ref{fig:merging}.
Otherwise, we fix $e_5$ and
instead perform vertex-merging on $z_6$ in the direction $\vec{v}$ as in the lower right picture.

Finally, the vertices $z_3, \dots, z_{d-1}$ with degree 3 are removed
and the pivot vertex $z_2$ becomes a vertex with degree $d$ to represent $x$ of $G$.
We repeat this procedure for all vertices of $G$ with degree larger than 3.
The resulting lattice presentation is now ambient isotopic to $G$.

We can always scale this presentation to fit into $\mathbb{Z}^{3}$
since there are only finitely many sticks which are parallel to $x$-, $y$- and $z$-axes.

\subsection{Reducing the number of sticks for arc cut-components} \label{subsec:arc} \hspace{10mm}

In Section~\ref{subsec:component},
two sticks are removed from each cut-component by side-sliding except from arc cut-components.
We now remove at least two sticks from each arc cut-component as well.

Let $G_k$ be an arc cut-component.
It has a unique stem cut-component $G_i$ and a unique branch cut-component $G_j$.
Even after vertex-merging,
we can take a cut-sphere $S$ separating $G_j$ from $G_k$ which intersects one endpoint $p$ of $G_k$.
We uniformly scale the ball bounded by $S$ small enough while fixing $p$.
This ball contains $G_j$ and all the branch cut-components of $G_j$.
We simply straighten the arc $G_k$ without touching the rest of $G$ as in Figure~\ref{fig:arccut}.
Obviously at least two sticks which are one $x$-stick and one $y$-stick
in the lattice presentation of $G_k$ are removed.

We again scale this presentation to fit into $\mathbb{Z}^{3}$.

\begin{figure}[h]
\includegraphics{fig11.eps}
\caption{Reducing the number of sticks for arc cut-components}
\label{fig:arccut}
\end{figure}

\subsection{Calculation} \label{subsec:cal} \hspace{10mm}

We now count the number of sticks necessary to construct the resulting lattice presentation $L$ of $G$.
Since one pair of $x$- and $y$-sticks comes from each arc of the lattice arc diagram,
$L$ initially had $\alpha(G)$ $x$-sticks and $\alpha(G)$ $y$-sticks.
As the result of side-sliding on each cut-component, we may reduce two more $x$- or $y$-sticks.
For each of the $\beta$ ($=\alpha(G)+v-e$ by Lemma~\ref{lem:binding}) binding points, we need at least one $z$-stick.
For each vertex $x$ with ${\rm d}(x) \! = \! 3$, one additional $z$-stick is necessary, and
for each vertex $x$ with ${\rm d}(x) \! \geq \! 4$,
we additionally need ${\rm d}(x) \! - \! 2$ $z$-sticks
and ${\rm d}(x) \! - \! 3$ $x$-sticks or $y$-sticks as the result of vertex-merging.
In summary,  the number of sticks of $L$ is
\begin{align*}
& 2\alpha(G)-2s+(\alpha(G)-e+v)+ \sum_{{\rm d}(x) = 3} 1 + \sum_{{\rm d}(x) \geq 4}(2{\rm d}(x)-5) \\
& = 3\alpha(G)-e+v-2s+\sum_{x \in V} (2{\rm d}(x)-5)+\sum_{{\rm d}(x) = 2} 1 \\
& = 3\alpha(G)-e+v-2s+2(2e)-5v+k \\
& = 3\alpha(G)+3e-4v-2s+k.
\end{align*}

Finally, we get
\begin{align*}
s_{L}(G)	& \leq 3\alpha(G)+3e-4v-2s+k \\
	& \leq 3c(G)+6e-4v-2s+3b+k,
\end{align*}
by applying Theorem~\ref{thm:LNO1}.
This completes the proof of Theorem~\ref{thm:bound}.


TITLE: Finding the 'n'th k-permutation of a set, and finding 'n' for a given k-permutation (lexicographical ordering)
QUESTION [0 upvotes]: Suppose you have a set, and want to order the k-permutations of the set (for example, the permutations of 5 elements of the set {1, 2, 3, ..., 16}). Is there a fast way of finding 'n' (the "lexicographical index") for, say {3, 16, 4, 11, 7}, and a fast way of finding the 5-permutation such that n = 100000?

REPLY [1 votes]: When you say fast, what do you mean?
If you mean a faster way than actually compute all the k-permutations, you actually can treat the problem as finding some element in a base(here the basis coefficients are gonna be Permutation numbers).For example, if you give me the set $[p]=\{1,\ldots ,p\}$, an integer q and an index i you must iteratively compute $\lfloor \frac{i}{\binom{p-n-1}{q-1-n}*(q-1-n)!} \rfloor+1$ (where $\binom{p-n-1}{q-1-n}*(q-1-n)!$ states because you want to choose the other numbers that are gonna be in the sequence and they have an order)and then decrement i in the residue. For example, suposse you want to calculate the 837th 3-permutation of $[16]$. The first element would be $\lfloor  \frac{837}{\binom{16-0-1}{3-1-0}*(3-1-0)!}\rfloor +1= \lfloor  \frac{837}{\binom{15}{2}*2!}\rfloor+1=\lfloor  \frac{837}{210}\rfloor+1=4$ then you update the i as $837-210*\lfloor  \frac{837}{210}\rfloor=207$
$\lfloor  \frac{207}{\binom{16-1-1}{3-1-1}*(3-1-1)!}\rfloor +1= \lfloor  \frac{207}{\binom{14}{1}*1!}\rfloor+1=\lfloor  \frac{207}{14}\rfloor+1=15$ but you put 4, so it's gonna be 16.
update i as $207-14*\lfloor\frac{207}{14}\rfloor=11$ but because you put 4,it's gonna be 13.
So the 3-permutation in $[16]$ with index 837 is $\{4,16,13\}$.
I think the complexity is gonna be $O(p*q)$.
For the inverse problem its the same Suposse i give $(a_1,\ldots a_q)$, the index of that permutation in $[p]$ is going to be like $(a_1-1)*\binom{p-1}{q-1}*(q-1)!+(a_2-1-[a_1<a2])*\binom{p-2}{q-2}(q-2)!+\ldots+(a_q-1-|\{j:a_j<a_q\}|)*\binom{p-q}{q-q}*(q-q)!$ I think this must be $O(p*q)$ also because of the binomial numbers.


TITLE: finding determinants using different properties
QUESTION [1 upvotes]: The equation is as follows:
$\operatorname{det}(2A^{-1} + 7\operatorname{adj}(A))$
Here I know that $\operatorname{det}(A^{-1}) = (\operatorname{det}(A))^{-1}$ and $\operatorname{det}(kA) = k^n \operatorname{det}(A)$
using these, we know that $\operatorname{det}((2A)^{-1} )= \frac{1}{4} \operatorname{det}(A)^{-1} =\frac{1}{8}$
I do not know a formula that relates to adjoints in this case besides maybe:
$$A \operatorname{adj}(A) = \operatorname{det}(A)I$$

REPLY [1 votes]: Look at this:
since
$A\operatorname{adj}(A) = \det(A)I, \tag{1}$
we have
$\operatorname{adj}(A) = \det(A) A^{-1} \tag{2}$
provided $A^{-1}$ exists.  Well, since we are given that (see comments above)
$\det(A) = 2, \tag{3}$
we know $A^{-1}$ does indeed exist, so using (2) we have
$2A^{-1} + 7\operatorname{adj}(A) = 2A^{-1} + 7\det(A)A^{-1} = (2 + 7\det(A))A^{-1}$
$= (2 + 7(2))A^{-1} = 16A^{-1}, \tag{4}$
whence
$\det(2A^{-1} + 7\operatorname{adj}(A)) = \det(16A^{-1}) = (16)^n (\det(A))^{-1},\tag{5}$
where $n = \operatorname{size}(A)$.  Now since
$\operatorname{det}((2A)^{-1} )= \frac{1}{4} \operatorname{det}(A)^{-1} =\frac{1}{8}, \tag{6}$
with
$\det(2A) = 2^n \det(A) \tag{7}$
and
$\det((2A)^{-1}) = (\det(2A))^{-1}, \tag{8}$
we see that
$2^{-n} = \dfrac{1}{4}, \tag{9}$
which shows that $n = 2$; thus (5) yields
$\det(2A^{-1} + 7\operatorname{adj}(A)) = \det(16A^{-1})$
$= (16)^2(\det(A))^{-1} = 256 (\det(A))^{-1} = \dfrac{256}{2} = 128.\tag{10}$


TITLE: Logic - Rearranging CNF formula
QUESTION [2 upvotes]: Given a #2SAT problem such as

how many ways can $(a \vee b) \wedge (\bar{a} \vee d) \wedge (\bar{b} \vee c) \wedge (\bar{c} \vee d)$ be satisfied?

I am trying to find a way to rearrange the clauses into collections of independent clauses. For this particular example, a desirable rearrangement would look like
$\big((a \vee b) \wedge (\bar{c} \vee d)\big) \wedge \big((\bar{b} \vee c) \wedge (\bar{a} \vee d)\big)$
since each of the two groupings contain each literal only once. My aim is to separate out the clauses in this way so that there are as a few groupings as possible. The example began with 4 groupings of 1 clause, the rearrangement has 2 groupings of 2 clauses.
A lower bound for the number of groupings is the number of times a literal appears. In this example, each literal appears twice so the number of groupings is at least 2.
My first thought was to represent each clause as a vertex of a graph and draw an edge between each pair of clauses that could be paired together. I would then search for the largest clique, then the next largest and so on. But this appears to be an NP-complete problem.
I am trying to find polynomial-time tools to perform this rearrangement.
Any help or direction is appreciated.

REPLY [1 votes]: Your problem is pretty "inherently" NP-Complete. You are trying to solve a graph coloring problem.
As you described, imagine your graph with clauses as vertices, and clauses that share variables have an edge. Suppose you have a solution with m groupings. Then take m colors, and color each vertex with the number based on which grouping that vertex is in. It will give you an m-coloring of the graph.
Asking if your problem can be solved in m groupings is equivalent to asking if there is an m coloring of the graph. Finding minimal colorings of graphs is NP-Complete.
Technically, this doesn't prove that your problem is NP-Complete, because not every graph will arise from a #2SAT problem. (The graphs you are getting are precisely the set of induced subgraphs of a "grid graph", that is, the conormal product of complete graphs.) But it is very strong evidence that your problem is NP-Complete.
For a solution to your problem, I would download some graph coloring software. Think carefully about whether you need the true optimum or just a decent approximation.