stabbing -- a follow up

[Ian Sanders]

Hi again,

Yesterday I posted:

>Normally I would not bother people with something like this but I have
>some >time pressures so I hope you will give me a bit of slack.
>
>I have been told that the problem I have been working on is "just like
>>stabbing" and so I wanted to check this out. Unfortunately it seems that
>most >of the literature that I can find is either not available in SA or
>if the >journals are available here then they are currently out. Would
>anyone be >prepared to give me a quick summary of stabbing/stabbers -- I
>am interested in >the 2-d case only as my problem is strictly 2-d. A
>summary would help me decide >whether to spend the money on inter-library
>loans from outside of South Africa >(an expensive process) to get copies
>of the papers.

To which Seth Teller replied:

>it might make more sense for you to post a brief
>description of your problem to the group.  then
>if people recognize similarities to stabbing we
>can point you to specific papers (many of which
>are online).
>
>seth.

A good suggestion! So further indulging your patience below follows a quick
summary of my problem;

\section{Statement of the Problem}\label{convex-statement}
Given a number of adjacent convex polygons (2-d as is all of my work
currently) find the fewest axial lines contained wholly inside the polygons
which will
cross all of the shared boundaries (adjacencies) between adjacent polygons.
An additional requirement is that each axial line should cross as many of
the shared boundaries as possible -- a \emph{maximal} axial line.

%%note an axial line is simply a line segment
%%note polygons are strictly non-overlapping.

As before, depending on how the problem is considered there are 2 similar but
distinct problems which can be addressed.
\begin{enumerate}
\item Adjacencies can be crossed more than once but every adjacency
must be crossed \emph{at least} once.
\item Any adjacency has \emph{exactly} one line crossing it.
\end{enumerate}

Here only problem $1$ is addressed. An example of the problem is shown in
Figure~\ref{convex-problem-example}.
\begin{figure}
\begin{center}
\begin{picture}(396,360)(0,0)
\put(0,0){\framebox(396,360){}}
\fboxsep=0pt
    \psset{unit=1pt}
    \begin{pspicture}(0,0)(396,360)
    \psset{fillstyle=solid,linestyle=solid,linewidth=0,bordercolor=black}

\pspolygon[fillcolor=lightgray](40,160)(45,200)(120,200)(160,160)(80,80)(45,85)
\pspolygon[fillcolor=lightgray](40,200)(40,280)(120,320)(120,240)(80,200)

\pspolygon[fillcolor=lightgray](120,200)(120,280)(200,240)(200,160)(160,160)

\pspolygon[fillcolor=lightgray](80,40)(80,80)(120,120)(240,140)(280,120)(200,40)

\pspolygon[fillcolor=lightgray](200,160)(200,240)(240,280)(280,280)(280,120)
    \pspolygon[fillcolor=lightgray](280,120)(280,200)(316,200)(356,160)

\pspolygon[fillcolor=lightgray](280,200)(280,280)(320,296)(360,260)(360,200)
    \psline(64,92)(300,140)
    \psline(52,204)(304,148)
    \psline(80,268)(312,196)
\end{pspicture}
\end{picture}
\end{center}
\label{convex-problem-example}
\caption{An example of placing axial lines to cross all of the
adjacencies in a configuration of adjacent convex polygons}
\end{figure}

The decision problem can be stated as \textit{\textbf{ALP-ALCP}}\\
\emph{Instance:} A collection of convex polygons $P_1 \ldots P_n$,
where each polygon is adjacent to at least one other polygon, and a
positive integer $M$.\\
\emph{Question:} Is there a set $L$ of axial lines where each axial
line is maximal in length, each line is wholly contained in the
collection of polygons, each shared boundary between adjacent polygons
is crossed at least once and $\mid L \mid \leq M$?\\

\begin{theorem}
\textit{\textbf{ALP-ALCP}} is NP-Complete.
\label{general}
\end{theorem}
I have proved this result.

Thanks again.

Ian



----------------------------------------------------------------
Ian Sanders                         Telephone:  (2711) 717-6187
School of Computer Science          Fax:        (2711) 717-6199
University of the Witwatersrand
Private Bag 3                       email:    ian at cs.wits.ac.za
2050 WITS SOUTH AFRICA            http://www.cs.wits.ac.za/~ian



-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.