Raymond Plante
Doug Roberts
% R.\ M.\ Crutcher\altaffilmark{1}
% Leave intact % Place the text of your abstract here The main scientific characteristic of VIMOS (VIsible Multi Object Spectrograph, to be placed on ESO Very Large Telescope) is its high multiplexing capability, allowing astronomers to obtain up to 800 spectra per exposure. To fully exploit such a potential a dedicated tool, the VIMOS Mask Preparation Software (MPS), has been designed. The MPS provides the astronomer with tools for the selection of the objects to be spectroscopically observed, including interactive object selection, handling of curved slits, and an algorithm for automatic slit positioning that derives the most effective solution in terms of number of object selected per field. The slit positioning algorithm must take into account both the initial list of user's preferred objects, and the constraints imposed either by the instrument characteristics or by the requirement of having easily reduceable data. The number of possible slit combinations in a field is in any case very high ($10^{73}$), and the task of slits maximization cannot be solved through a purely combinational approach. We have introduced an innovative approach, based on the analysis of the function (Number of slits)/(slit length) vs. (slit length). The algorithm has been fully tested with good results, and it will be distributed to the astronomical community for the observation preparation phase.
P1-26.tex
%ADASS_PROCEEDINGS_FORM%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% TEMPLATE.TEX -- ADASS VIII (98) ASP Conference Proceedings template
% Updated by N. Manset for ADASS IX (99) and F. Primini for ADASS 2000.
%
% Use this template to create your proceedings paper in LaTeX format
% by following the instructions given below.  Much of the input will
% be enclosed by braces (i.e., { }).  The percent sign, "%", denotes
% the start of a comment; text after it will be ignored by LaTeX.  
% You might also notice in some of the examples below the use of "\ "
% after a period; this prevents LaTeX from interpreting the period as
% the end of a sentence and putting extra space after it.  
% 
% You should check your paper by processing it with LaTeX.  For
% details about how to run LaTeX as well as how to print out the User
% Guide, consult the README file.  (The User Guide is also available
% on-line via http://hea-www.harvard.edu/ADASS/ in the Proceedings
% section) You should also consult the sample LaTeX papers,
% sample1.tex and sample2.tex, for examples of including figures, html
% links, special symbols, and other advanced features.
%
% If you do not have access to the LaTeX software or a laser printer
% at your site, you can still prepare your paper following the
% instructions in the User Guide.  In such cases, the editors will
% process the file and make any necessary editorial adjustments.
% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 
\documentstyle[11pt,adassconf]{article}  % Leave intact

\begin{document}   % Leave intact

%-----------------------------------------------------------------------
%			    Paper ID Code
%-----------------------------------------------------------------------
% Enter the proper paper identification code.  The ID code for your
% paper is the session number associated with your presentation as
% published in the official ADASS 2000 conference program.  You can
% find this number locating your abstract in the printed program
% that you received at the meeting or on-line via
% http://hea-www.harvard.edu/ADASS/; the ID code is the letter-number
% sequence proceeding the title of your presentation.
%
% This will not appear in your paper; however, it allows different
% papers in the proceedings to cross-reference each other.
%
% EXAMPLE: \paperID{O1-03}
% EXAMPLE: \paperID{P2-56}
%
% Note that you should only have one \paperID, and it should not
% include a trailing period.  

\paperID{P1-26 }

%-----------------------------------------------------------------------
%		            Paper Title 
%-----------------------------------------------------------------------
% Enter the title of the paper.
%
% EXAMPLE: \title{}
% 

\title{The VIMOS Mask Preparation Software}

%-----------------------------------------------------------------------
%		          Authors of Paper
%-----------------------------------------------------------------------
% Enter the authors followed by their affiliations.  The \author and
% \affil commands may appear multiple times as necessary (see example
% below).  List each author by giving the first name or initials first
% followed by the last name.  Authors with the same affiliations
% should grouped together. 
%
% EXAMPLE: \author{Raymond Plante, Doug Roberts, 
%                  R.\ M.\ Crutcher\altaffilmark{1}}
%          \affil{National Center for Supercomputing Applications, 
%                 University of Illinois Urbana-Champaign, Urbana, IL
%                 61801}
%          \author{Tom Troland}
%          \affil{University of Kentucky}
%
%          \altaffiltext{1}{Astronomy Department, UIUC}
%
% In this example, the first three authors, "Plante", "Roberts", and
% "Crutcher" are affiliated with "NCSA".  "Crutcher" has an alternate 
% affiliation with the "Astronomy Department".  The fourth author,
% "Troland", is affiliated with "University of Kentucky"

\author{Dario Bottini\altaffilmark{1}, Bianca Garilli}
\affil{Istituto di Fisica Cosmica G. Occhialini, CNR, Milano}

\author{Laurence Tresse}
\affil{Laboratoire d'Astrophysique de Marseille, France}
\altaffiltext{1}{On behalf of the VIRMOS Consortium}


%-----------------------------------------------------------------------
%			 Contact Information
%-----------------------------------------------------------------------
% This information will not appear in the paper but will be used by
% the editors in case you need to be contacted concerning your
% submission.  Enter your name as the contact along with your email
% address.
% 
% EXAMPLE:  \contact{Dennis Crabtree}
%           \email{crabtree@cfht.hawaii.edu}
%

\contact{Dario Bottini}
\email{bottini@ifctr.mi.cnr.it}

%-----------------------------------------------------------------------
%		      Author Index Specification
%-----------------------------------------------------------------------
% Specify how each author name should appear in the author index.  The 
% \paindex{ } should be used to indicate the primary author, and the
% \aindex for all other co-authors.  You MUST use the following
% syntax: 
%
% SYNTAX:  \aindex{LASTNAME, F. M.}
% 
% where F is the first initial and M is the second initial (if
% used).  This guarantees that authors that appear in multiple papers
% will appear only once in the author index.  
%
% EXAMPLE: \paindex{Crabtree, D.}
%          \aindex{Manset, N.}        
%          \aindex{Veillet, C.}        

\paindex{Bottini, D.}
\aindex{Garilli, B.}     % Remove this line if there is only one author
\aindex{Tresse, L.}     % Remove this line if there is only one author
%-----------------------------------------------------------------------
%			Subject Index keywords
%-----------------------------------------------------------------------
% Enter up to 6 keywords describing your paper.  These will NOT be
% printed as part of your paper; however, they will be used to
% generate the subject index for the proceedings.  There is no
% standard list; however, you can consult the indices for past ADASS
% proceedings (http://iraf.noao.edu/ADASS/adass.html). 
%
% EXAMPLE:  \keywords{visualization, astronomy: radio, parallel
%                     computing, AIPS++, Galactic Center}
%
% In this example, the author noticed that "radio astronomy" appeared
% in the ADASS VII Index as "astronomy" being the major keyword and
% "radio" as the minor keyword.

\keywords{spectroscopy: computing}

%-----------------------------------------------------------------------
%			       Abstract
%-----------------------------------------------------------------------
% Type abstract in the space below.  Consult the User Guide and Latex
% Information file (http://hea-www.harvard.edu/ADASS/ in the
% Proceedings section) for a list of supported macros (e.g. for
% typesetting special symbols). 

\begin{abstract}          % Leave intact
% Place the text of your abstract here 

The main scientific characteristic of VIMOS (VIsible Multi Object
Spectrograph, to be placed on ESO Very Large Telescope) is its high
multiplexing capability, allowing astronomers to obtain up to 800
spectra per exposure. To fully exploit such a potential a dedicated
tool, the VIMOS Mask Preparation Software (MPS), has been designed.
The MPS provides the astronomer with tools for the selection of the
objects to be spectroscopically observed, including interactive object
selection, handling of curved slits, and an algorithm for automatic
slit positioning that derives the most effective solution in terms of
number of object selected per field.  The slit positioning algorithm
must take into account both the initial list of user's preferred
objects, and the constraints imposed either by the instrument
characteristics or by the requirement of having easily reduceable
data.  The number of possible slit combinations in a field is in any
case very high ($10^{73}$), and the task of slits maximization cannot
be solved through a purely combinational approach. We have introduced
an innovative approach, based on the analysis of the function (Number
of slits)/(slit length) vs. (slit length). The algorithm has been
fully tested with good results, and it will be distributed to the
astronomical community for the observation preparation phase.

\end{abstract}

%-----------------------------------------------------------------------
%			      Main Body
%-----------------------------------------------------------------------
% Place the text for the main body of the paper here.  You should use
% the \section command to label the various sections; use of
% \subsection is optional.  Significant words in section titles should
% be capitalized.  Sections and subsections will be numbered
% automatically. 
%
% EXAMPLE:  \section{Introduction}
%           ...
%           \subsection{Our View of the World}
%           ...
%           \section{A New Approach}
%
% It is recommended that you look at the sample papers, sample1.tex
% and sample2.tex, for examples for formatting references, footnotes,
% figures, equations, html links, lists, and other special features.  

\section{Introduction}

The VIRMOS (Visible and Infrared Multi-Object Spectrograph) project
consists of two spectrographs with enhanced survey capabilities to be
installed on two unit telescopes of ESO Very Large Telescope (Chile):
VIMOS (0.37-1 $\mu m$) and NIRMOS (0.9-1.85 $\mu m$), each one having
a large field of view (~14'x16') split into 4 quadrants and a high
multiplexing factor (up to approximately 800 spectra per exposure).

To easily exploit such a potential a dedicated tool, the VIRMOS Mask
Preparation Software (MPS), has been implemented.  It provides the
astronomer with tools for the selection of the objects to be
spectroscopically observed, and for automatic slit positioning.  The
output of MPS is used to build the slit masks to be mounted in the
instrument for the spectroscopic observations.


\section{Requirements}

At a limiting magnitude $_I < 24$, the density of objects in the
sky is such that more than 1000 galaxies are visible in a VIMOS
quadrant. Of course, not all these objects can be spectroscopically
observed, as some requirements imposed by data quality have to be
taken into account when placing slits: the minimum slit length will
depend on the object size, since the slit must contain some area of
``pure sky'' to allow for a reliable sky subtraction; spectra must not
overlap either along the dispersion or the spatial direction; as each
first order spectrum is coupled with a second order spectrum which
will contaminate the first order spectrum of the slit above, a good
sky subtraction can be performed only if slits are aligned in columns
(same spatial coordinate) and, within the same column, have the same
length.  All these factor lead to a theoretical maximum number of
spectra per quadrant of approximately 200.

Another requirement for MPS is set by the very good VLT seeing which
allows the use of slits widths of 0.3-0.4 arcsec. Such narrow slits
imply an extremely precise slit positioning, with maximum
uncertainties of the order of 0.1 arcsec. Thus the need for some (1-2
per quadrant) manually selected reference objects (possibly bright and
point-like) to be used for mask alignment.  Moreover, the user must
have the possibility to manually choose some particularly interesting
sources to be included (Compulsory objects) and some others to be
excluded (Forbidden objects) from the spectroscopic sample.  Also a
tool for manual definition of curved or tilted slits, to better follow
the shape of particularly interesting objects, has to be provided.

The MPS works starting from a VIMOS image, to which a catalogue of
objects is associated.  The catalogue can be derived from the image
itself or from some other astronomical data-set.  In this second case,
a way to correlate the celestial coordinates of the objects in the
catalogue with image coordinates is to be provided.  Some catalog
handling capabilities, to allow for the selection of classes of sources
among which to operate the choice of spectroscopic targets, some image
display and catalogue overlay capabilities have to be provided by the
package.


\section{MPS Graphical User's Interface}

As MPS will be distributed to the astronomical community, it should be
based on some already known package (Not Yet Another System).  It was
therefore decided to base the MPS GUI on the SKYCAT tool distributed
by ESO (see \verb1http://archive.eso.org:8080/skycat/1).  This tool 
allows astronomers to couple VIMOS images and catalogues on which to 
operate selections of objects over which to place slits.

A new panel for catalogue display, for object selection (Reference,
Compulsory, Forbidden object) has been implemented.  For each type of
catalogue objects a different overlay symbol has been defined.


\subsection{Curved/tilted slits definition}

A dedicated zoom panel allows the definition of curved/tilted slits.
Curved slits are defined by fitting a Bezier curve to a set of points
chosen by the user by clicking on the zoom display. The fitted curve
is then automatically plotted.  The slit width is chosen through a scale
widget.

Tilted slits can be defined as curved slits and then straightened.  If
the astronomer wants to have slits of a width different from the one
chosen for the automatic slit placements, he can define them as tilted
slits and then align them to the other automatically placed slits.


\section{Slit Positioning Optimization Code}

The core of Mask Preparation Software is the Slit Positioning
Optimization Code (SPOC). Given a catalog of objects, SPOC maximizes
the number of observable objects in a single exposure and computes the
corresponding slit positions.

SPOC places slits on the field of view taking into account: special
objects (reference, compulsory, forbidden), special slits (curved,
tilted or user's dimension defined), spectral first order
superposition, spectral higher order superposition and sky region
parameter (the minimum amount of sky to be added to an object size
when defining a slit).


\subsection{The Optimization}

The issue to be solved is a combinatory computational problem.
Because of the constraint of slits aligned in the dispersion
direction, the problem can be slightly simplified: the quadrant area
can be considered as a sum of strips which are not necessarily of the
same width in the spatial direction. Slits within the same strip have
the same length and the alignment of orders is fully ensured.  The
problem is thus reduced to be mono-dimensional.  It is easy to show
that the number of combination is roughly given by: $N_{combination} =
(N_{possible~ strip~ widths})^{(average~ number~ of~ strips)}$ The
slit length (or strip width) can vary from a minimum of 4 arcsec (20
pixels, i.e. twice the minimum sky region required for the sky
subtraction) to a maximum of 30 arcsec (150 pixels, limit imposed by
the slit laser cutting machine).  The average number of strips can be
estimated as the spatial direction size of the FOV divided by the most
probable slit length: assuming the latter to be 50 pixels (10 arcsec),
we would have $2048/50 = 41$ strips. The number of combinations would
then be: $N_{combinations} = 130^{41} \simeq 4.7\times10^{86}$.
Computing these many combinations would correspond to $10^{60}$ years
of CPU work!  The problem is similar to the well known traveling
salesman problem: in the standard approach, this is solved by randomly
extracting a "reasonable" number of combinations and maximizing over
this subsample. In our case, due to computational time, the
"reasonable" number of combinations cannot be higher than $10^8-10^9$,
so small with respect to the total number of combination that the
result is not guaranteed to be near the real maximum. Our approach has
been to consider only the most "probable" combinations, i.e. the ones
that have the highest probability to maximize the solution.

Step 1: For each spatial coordinate, we can vary the strip width from
the given minimum to the given maximum, count how many objects we can
place in the strip, and build the diagram of the number of slits in a
strip divided by the strip width as a function of the strip width. For
each spatial coordinate, only the strip widths corresponding to peaks
in this histogram are worth considering, as they correspond to local
maxima of the number of slits per strip.  The exact positioning of the
peaks varies for each spatial coordinate, but the shape of the
function remains the same. The position of the peaks can be easily
found in no more than 6-7 trials (using a partition exchange method).

Step 2 For each spatial coordinate we have K (where K is the number of
peaks) possible strips, each with its own length and number of slits.
Although the number of combinations to be tested is decreased it is
still too big in terms of computational time.  

Step 3 A further reduction can be obtained if, instead of considering
all the strips simultaneously, we consider sequentially M subsets of N
consecutive strips, which together cover the whole FOV. At this point,
we should vary N (and consequently M) to find the best solution. In
practice, when N is higher than 8-10, nothing changes in terms of
number of observable objects. For N=10, thus M=4
(i.e. $2048/(4\times50)$), the number of combination is reduced to
only $4\times4^{10}=4\times10^6$, which means a few seconds of CPU
work.  Unfortunately, as a consequence of the optimization process,
small size objects are favored against the big ones.


\subsection{An alternative optimization}

A second, less optimized algorithm, has been implemented within SPOC.
This alternative algorithm does not optimize all strips simultaneously
but builds the $N_{Slit}/Strip$ function strip by strip without
considering object sizes, and takes only the maximum of the
distribution. Then it enlarges each strip width by taking into account
object sizes.  In this way the number of placed slits decreases by a
few percent but the object dimension bias disappears.


\section{SPOC Graphical User Interface}

A dedicated panel for SPOC set up has been implemented within SKYCAT.
Trough this panel, users can select the grism, the slit width, and the
sky region parameter, the number of masks to be obtained for the given
field, and the type of SPOC maximization.
 
The number of input slit and placed slit for all kinds of objects
(Reference, Compulsory, etc...)  is printed in a text box.

The slit catalogue produced by SPOC can be loaded as a normal SKYCAT
catalog with overlay symbols defined for all kinds of objects, and it
is also possible to plot the slit and spectrum overlay for all SPOC
catalog objects.


%-----------------------------------------------------------------------
%			      References
%-----------------------------------------------------------------------
% List your references below within the reference environment
% (i.e. between the \begin{references} and \end{references} tags).
% Each new reference should begin with a \reference command which sets
% up the proper indentation.  Observe the following order when listing
% bibliographical information for each reference:  author name(s),
% publication year, journal name, volume, and page number for
% articles.  Note that many journal names are available as macros; see
% the User Guide
% (http://hea-www.harvard.edu/ADASS/ in the Proceedings section)
% listing "macro-ized" journals.   
%
% EXAMPLE:  \reference Hagiwara, K., \& Zeppenfeld, D.\  1986, 
%                Nucl.Phys., 274, 1
%           \reference H\'enon, M.\  1961, Ann.d'Ap., 24, 369
%           \reference King, I.\ R.\  1966, \aj, 71, 276
%           \reference King, I.\ R.\  1975, in Dynamics of Stellar 
%                Systems, ed.\ A.\ Hayli (Dordrecht: Reidel), 99
%           \reference Tody, D.\  1998, \adassvii, 146
%           \reference Zacharias, N.\ \& Zacharias, M.\ 2000,
%                \adassix, \paperref{P7.6}
% 
% Note the following tricks used in the example above:
%
%   o  \& is used to format an ampersand symbol (&).
%   o  \'e puts an accent agu over the letter e.  See the User Guide
%      and the sample files for details on formatting special
%      characters.  
%   o  "\ " after a period prevents LaTeX from interpreting the period 
%      as an end of a sentence.
%   o  \aj is a macro that expands to "Astron. J."  See the User Guide
%      for a full list of journal macros
%   o  \adassvii is a macro that expands to the full title, editor,
%      and publishing information for the ADASS VII conference
%      proceedings.  Such macros are defined for ADASS conferences I
%      through X.
%   o  When referencing a paper in the current volume, use the
%      \adassix and \paperref macros.  The argument to \paperref is
%      the paper ID code for the paper you are referencing.  See the 
%      note in the "Paper ID Code" section above for details on how to 
%      determine the paper ID code for the paper you reference.  
%

%\begin{references}

%\end{references}

% Do not place any material after the references section

\end{document}  % Leave intact
