Algorithms: Tiling of spectroscopy plates
Tiling is the process by which the spectroscopic plates are designed
and placed relative to each other. This procedure involves optimizing
both the placement of fibers on individual
plates, as well as the placement of plates (or tiles) relative to each
other.
 Introduction
 Spectroscopy Survey Overview
 What is Tiling?
 Fiber Placement
 Dealing with Fiber Collisions
 Tile Placement
 Technical Details
Introduction
Because of largescale structure in the galaxy distribution (which
form the bulk of the SDSS targets), a naive covering of the sky with
equallyspaced tiles does not yield uniform sampling. Thus, we present
a heuristic for perturbing the centers of the tiles from the
equallyspaced distribution to provide more uniform
completeness. For the SDSS sample, we can attain a sampling rate of
>92% for all targets, and >99% for the set of targets which do
not collide with each other, with an efficiency >90% (defined as
the fraction of available fibers assigned to targets).
Much of the content of this page can be found in the
SDSS
tiling paper Blanton et al. 2003, AJ 125, 2276.
The Spectroscopic Survey
The spectroscopic survey is performed using two multiobject fiber
spectrographs on the same telescope. Each spectroscopic
fiber plug plate, referred to as a ``tile,'' has a circular fieldofview
with a radius of 1.49 degrees, and can accommodate 640 fibers, 48 of
which are reserved for observations of blank sky and
spectrophotometric standards.Because of the finite size of the fiber
plugs, the minimum separation of fiber centers is 55''. If, for
example, two objects are within 55'' of each other, both of them can
be observed only if they lie in the overlap between two adjacent
tiles. The goal of the SDSS is to observe 99% of the maximal set of
targets which has no such collisions (about 90% of all targets).
What is Tiling?
Around 2,000 tiles will be necessary to provide fibers for all the
targets in the survey. Since each tile which must be observed
contributes to the cost of the survey (due both to the cost of
production of the plate and to the cost of observing time), we desire
to minimize the number of tiles necessary to observe all the desired
targets. In order to maximize efficiency (defined as the fraction of
available fibers assigned to tiled targets) when placing these tiles
and assigning targets to each tile, we need to address two
problems. First, we must be able to determine, given a set of tile
centers, how to optimally assign targets to each tile  that is, how
to maximize the number of targets which have fibers assigned to them.
Second, we must determine the most efficient placement of the tile
centers, which is nontrivial because the distribution of targets on
the sky is nonuniform, due to the wellknown clustering of galaxies
on the sky. We find the exact solution to the first problem and use a
heuristic method developed by Lupton et al. (1998) to find an
approximate solution to the second problem (which is NPcomplete).
The code which implements this solution is designed to run on a patch of sky
consisting of a set of rectangles in a spherical coordinate system,
known in SDSS parlance as a tiling region.
NOTE: the term ``chunk'' or ``tiling chunk'' is sometimes
used to denote a tiling region. To avoid confusion with the
correct use of the term chunk, we use ``tiling region'' here.
Fiber Placement
First, we discuss the allocation of fibers given a set of tile
centers, ignoring fiber collisions for the moment.
Figure 1 shows at the left a very simple example of a
distribution of targets and the positions of two tiles we want to use
to observe these targets. Given that for each tile there is a finite
number of available fibers, how do we decide which targets get
allocated to which tile? This problem is equivalent to a network flow
problem, which computer scientists have been kind enough to solve for us
already.
 
Figure 1: Simplified Tiling and Network Flow View 
The basic idea is shown in the right half of Figure 1,
which shows the appropriate network for the situation in the left
half. Using this figure as reference, we here define some terms
which are standard in combinatorial literature and which will be
useful here:
 node: The nodes are the solid dots in the figure; they
provide either sources/sinks of objects for the flow or simply serve
as junctions for the flow. For example, in this context each target
and each tile corresponds to a node.
 arc: The arcs are the lines connecting the nodes. They
show the paths along which objects can flow from node to node. In
Figure 1, it is understood that the flow along the arc
proceeds to the right. For example, the arcs traveling from target
nodes to tile nodes express which tiles each target may be assigned
to.
 capacity: The minimum and maximum capacity of each arc is
the minimum and maximum number of objects that can flow along it. For
example, because each tile can accommodate only 592 target fibers, the
capacities of the arcs traveling from the tile nodes to the sink node
is 592.
 cost: The cost per object along each arc is exacted for
allowing objects to flow down a particular arc; the total cost is the
summed cost of all the arcs. In this paper, the network is designed
such that the minimum total cost solution is the desired solution.
Imagine a flow of 7 objects entering the network at
the source node at the left. We want the entire flow to leave
the network at the sink node at the right for the lowest possible
cost. The objects travel along the arcs, from node to node. Each
arc has a maximum capacity of objects which it can transport, as
labeled. (One can also specify a minimum number, which will be
useful later). Each arc also has an associated cost, which is exacted
per object which is allowed to flow across that arc. Arcs link the
source node to a set of nodes corresponding to the set of
targets. Each target node is linked by an arc to the node of each tile
it is covered by. Each tile node is linked to the sink node by an arc
whose capacity is equal to the number of fibers available on that
tile. None of these arcs has any associated cost. Finally, an
``overflow'' arc links the source node directly to the sink node, for
targets which cannot be assigned to tiles. The overflow arc has
effectively infinite capacity; however, a cost is assigned to objects
flowing on the overflow arc, guaranteeing that the algorithm fails to
assign targets to tiles only when it absolutely has to. This network
thus expresses all the possible fiber allocations as well as the
constraints on the numbers of fibers in each tile. Finding the
minimum cost solution then maximizes the number of targets
which are actually assigned to tiles.
Dealing with Fiber Collisions
As described above, there is a limit of 55'' to how close two fibers
can be on the same tile. If there were no overlaps between tiles,
these collisions would make it impossible to observe ~10% of
the SDSS targets. Because the tiles are circular, some fraction of
the sky will be covered with overlaps of tiles, allowing some of these
targets to be recovered. In the presence of these collisions, the
best assignment of targets to the tiles must account for the presence
of collisions, and strive to resolve as many as possible of these
collisions which are in overlaps of tiles. We approach this problem
in two steps, for reasons described below. First, we apply the network
flow algorithm of the above section to the
set of ``decollided''
targets  the largest possible subset of the targets which do not
collide with each other. Second, we use the remaining fibers and a
second network flow solution to optimally resolve collisions in
overlap regions.

Figure 2: Fiber Collisions 
The "decollided" set of targets is the maximal subset of targets which
are all greater than 55'' from each other. To clarify what we mean by
this maximal set, consider Figure 2. Each circle represents a target;
the circle diameter is 55'', meaning that overlapping circles are
targets which collide. The set of solid circles is the ``decollided''
set. Thus, in the triple collision at the top, it is best to keep the
outside two rather than the middle one.
This determination is complicated slightly by the fact that some
targets are assigned higher priority than others. For example, as
explained in the Targetting pages, QSOs are
given higher priority than
galaxies by the SDSS target selection algorithms. What we mean here by
``priority'' is that a higher priority target is guaranteed never to
be eliminated from the sample due to a collision with a lower priority
object. Thus, our true criterion for determining whether one set of
assignments of fibers to targets in a group is more favorable than
another is that a greater number of the highest priority objects are
assigned fibers.
Once we have identified our set of decollided objects, we use the
network flow solution to find the best possible assignment of fibers
to that set of objects.
After allocating fibers to the set of decollided
targets, there will
usually be unallocated fibers, which we want to use to resolve
fiber collisions in the overlaps. We can again express the problem of
how best to perform the collision resolution as a network, although
the problem is a bit more complicated in this case. In the case of
binaries and triples, we design a network flow problem such that the
network flow solution chooses the tile assignments optimally. In the
case of higher multiplicity groups, our simple method for binaries and
triples does not work and we instead resolve the fiber collisions in a
random fashion; however, fewer than 1% of targets are in such groups,
and the difference between the optimal choice of assignments and the
random choices made for these groups is only a small fraction of that.
We refer the reader to the tiling
algorithm paper for more details, including how the fiber
collision network flow is designed and caveats about what
aspects of the method may need to be changed under different
circumstances.
Tile Placement
Once one understands how to assign fibers given a set of tile centers,
one can address the problem of how best to place those tile centers.
Our method first distributes tiles
uniformly across the sky and then uses a costminimization scheme to
perturb the tiles to a more efficient solution.
In most cases, we set initial conditions by simply laying down a
rectangle of tiles. To set the centers of the tiles along the long
direction of the rectangle, we count the number of targets along the
stripe covered by that tile. The first tile is put at the mean of the
positions of target 0 and target N_t, where N_t
is the number of fibers per tile (592 for the SDSS). The second tile
is put at the mean between target N_t and 2N_t, and so on.
The counting of targets along adjacent stripes is offset by about half a
tile diameter in order to provide more complete covering.
The method is of perturbing this uniform distribution is iterative.
First, one allocates targets to the tiles, but instead of limiting a
target to the tiles within a tile radius, one allows a target to be
assigned to further tiles, but with a certain cost which increases
with distance (remember that the network flow accommodates the
assignment of costs to arcs). One uses exactly the same fiber
allocation procedure as above.
What this does is to give each tile some information about the
distribution of targets outside of it. Then, once one has assigned a
set of targets to each tile, one changes each tile position to that
which minimizes the cost of its set of targets. Then, with the new
positions,
one reruns the fiber
allocation, perturbs the tiles again, and so on. This method is guaranteed
to converge to a minimum (though
not necessarily a global minimum), because the total cost must
decrease at each step.
In practice, we also need to determine the appropriate number of tiles
to use. Thus, using a standard binary search, we repeatedly run the
costminimization to find the minimum number of tiles necessary to
satisfy the SDSS requirements, namely that we assign fibers to 99%
of the decollided targets.
In order to test how well this algorithm works, we have applied it
both to simulated and real data. These results are discussed in the
Tiling
paper.
Technical Details
There are a few technical details which may be useful to mention in
the context of SDSS data. Most importantly, we will describe which
targets within the SDSS are ``tiled'' in the manner described here,
and how such targets are prioritized. Second, we will discuss the
method used by SDSS to deal with the fact that the imaging and
spectroscopy are performed within the same fiveyear time
period. Third, we will describe the tiling outputs which the SDSS
tracks as the survey progresses. Throughout, we refer to the code
which implements the algorithm described above as tiling.
Only some of the spectroscopic target types identified by the target
selection algorithms in the SDSS are ``tiled.'' These types (and their
designations in the primary and secondary target bitmasks) are
described in the Targetting pages). They consist
of most types of QSOs, main sample galaxies,
LRGs, hot standard stars, and brown dwarfs. These are the types of
targets for which tiling is run and for which we are attempting to
create a welldefined sample. Once the code has guaranteed fibers to
all possible ``tiled targets,'' remaining fibers are assigned to other
target types by a separate code.
All of these target types are treated equivalently, except that they
assigned different ``priorities,'' designated by an integer. As
described above, the tiling code uses them to help decide fiber
collisions. The sense is that a higher priority object will never lose
a fiber in favor of a lower priority object. The priorities are
assigned in a somewhat complicated way for reasons immaterial to
tiling, but the essence is the following: the highest priority objects
are brown dwarfs and hot standards, next come QSOs, and the lowest
priority objects are galaxies and LRGs. QSOs have higher priority than
galaxies because galaxies are higher density and have stronger angular
clustering. Thus, allowing galaxies to bump QSOs would allow
variations in galaxy density to imprint themselves into variations in
the density of QSOs assigned to fibers, which we would like to avoid.
For similar reasons, brown dwarfs and hot standard stars (which have
extremely low densities on the sky) are given highest priority.
Each tile, as stated above, is 1.49 degrees in radius, and has
the capacity to handle 592 tiled targets. No two such targets may be
closer than 55'' on the same tile.
The operation of the SDSS makes it impossible to tile the entire
10,000 square degrees simultaneously, because we want to be able to
take spectroscopy during nonpristine nights, based on the imaging
which has been performed up to that point. In practice, periodically a
``tiling region'' of data is processed, calibrated, has targets
selected, and is passed to the tiling code. During the first year of
the SDSS, about one tiling region per month has been created; as more
and more imaging is taken and more tiles are created, we hope to
decrease the frequency with which we need to make tiling regions, and
to increase their size.
A tiling region is defined as a set of rectangles on the sky (defined in
survey
coordinates). All of these rectangles cover only sky which has
been imaged and processed. However, in the case of tiling, targets
may be missed near the edges of a tiling region because that area
was not covered by tiles. Thus, tiling is actually run on a somewhat larger area than a single tiling region, so the areas near the edges of adjacent
tiling regions are also included. This larger area is known as a tiling region. Thus, in general, tiling regions overlap.
The first tiling region which is ``supported'' by the SDSS is denoted
Tiling Region
4. The first tiling region for which the version of tiling described here was
run is Tiling Region 7. Tiling regions earlier than Tiling Region 7 used a different (less
efficient) method of handling fiber collisions. The earlier version
also had a bug which artificially created gaps in the distribution of
the fibers. The locations of the known gaps are given in the EDR paper for Tiling Region 4 as the overlaps
between plates 270 and 271, plates 312 and 313, and plates 315 and 363
(also known as tiles 118 and 117, tiles 76 and 75, and tiles 73 and
74).
Tiling Window
In order to interpret the spectroscopic sample, one needs to use
the information about how targets were selected, how the tiles were
placed, and how fibers were assigned to targets. We refer to the
geometry defined by this information as the "tiling window" and
describe how to use it in detail
elsewhere. As we note below, for the purposes of data release
users it is also important to understand what the photometric imaging
window which is released (including, if desired, masks for image
defects and bright stars) and which plates have been released.
Last modified: Tue Jul 26 21:59:25 CDT 2005
