Alex Szalay, Gyorgy Fekete, Tamas Budavari, Jim Gray, Adrian Pope, Ani
Thakar
August 2003, revised March 2004, December 2004, November 2005
The Problem
The SDSS spectroscopic survey will consist of about 2000 circular Tiles, each
about 1.5 deg. in radius, which contain the objects for a given spectroscopic
observation. There are more opportunities to target (get the spectrum of) an
object if it is covered by multiple tiles. If three tiles cover an area, the
objects in that area are three times more opportunity to be targeted. At the
same time, objects are not targeted uniformly over a plate. The targeting is
driven by a program that uses the SDSS photographic observations to schedule
the spectroscopic observations. These photographic observations are 2.5
deg. wide stripes across the sky. The strips overlap about 15%, so the sky is
partitioned into disjoint staves and the tiling is actually done in terms of
these staves (see Figure 1.) Staves are often misnamed stripes in the database
and in other SDSS documentation.
 |
| Figure 1. Observations consist of overlapping stripes
partitioned into disjoint staves. Tiling
Runs work on a set of staves, and each Tiling
Geometry region is contained within a stave. |
Spectroscopic targeting is done by a tiling run that works with a collection
of staves - actually not whole staves but segments of them called chunks. The
tiling run generates tiles that define which objects are going to be observed
(actually, which holes to drill in a SDSS spectroscopic plate.) The tiling
run also generates a list of TilingGeometry rectangular regions that describe
the sections of the staves that were used to make the tiles. Some
TilingGeometry rectangles are positive, others are negative (masks or holes.)
Subsequent tiling runs may use the same staves (chunks) and so tiling runs are
not necessarily disjoint. So, TilingGeometries form rather complex
intersections that we call SkyBoxes.
The goal is to compute contiguous sectors covered by some number of plates and
at least one positive TilingGeometry. We also want to know how many plates
cover the sector.
This is a surprisingly difficult task because there are subtle interactions.
We will develop the algorithm to compute sectors in steps. First we will
ignore the TilingGeometry and just compute the wedges (Boolean combinations of
tiles). Then we will build TilingBoxes, positive quadrilateral partitions of
each tiling region that cover the regions. SkyBoxes are the synthesis of the
TilingBoxes from several tiling runs into a partitioning of the survey
footprint into disjoint quadrilaterals positive quadrilaterals. Now, to
compute sectors, we simply intersect all wedges with all Skyboxes. The
residue is the tile coverage of the survey. A tile contributes to a sector if
the tile contributes to the wedge and the tile was created by one of the tile
runs that contain the SkyBox (you will probably understand that last sentence
better after you read to the end of this paper.)
Wedges
 |
| Figure 2. A wedge and
sector covered by one plate. There are adjoining wedges
covered by 2, 3, 4 plates. The lower left corner is an area that is
not part of any wedge or sector. SkyBoxes break wedges into
sectors and may mask parts of a wedge. |
A wedge is the intersection of one or more tiles or the intersection of some
tiles with the complements of some others. Each wedge has a depth: the number
of positive tiles covering the wedge (see figures 2, 3). The two intersecting
tiles in figure 2, A and B, have (A-B) and (B-A) wedges of depth 1, and the
intersection (AB) is a depth 2 wedge.
 |
| Figure 3. Tile A has a blue boundary;
tile B has the red boundary, both regions of depth
1. Their intersection is yellow, a Region of depth 2. The crescents
shaded in blue and green are the two wedges of
depth 1, and the yellow area is a wedge of
depth 2. Nodes are purple dots. |
A sector is a wedge modified by intersections with overlapping TilingGeometry
regions. If the TilingGeometry regions are complex (multiple convexes) or if
they are holes (isMask=1), then the result of the intersection may also be
complex (a region of multiple wedges). By going to a SkyBox model we keep
things simple. Since SkyBoxes partition the sky into areas of known tile-run
depth, SkyBox boundaries do not add any depth to the sectors; they just
truncate them to fit in the box boundary and perhaps mask a tile if that tile
is in a TilingGeometry hole or if the tile that contributes to that wedge is
not part of the TilingGeometry (one of the tiling runs) that make up that
SkyBox (Figure 4 shows a simple example of these concepts).
 |
| Figure 4.This shows how the tiles and
TilingGeometry rectangles intersect to form
sectors. On the figure we have a layout that has wedges
of various depths, depth 1 is gray, depth 2 is light blue, depth 3 is
yellow and depth 4 is magenta. The wedges are clipped by the
TilingGeometry boundary to form sectors. |
To get started, spCreateWedges() computes the wedge regions, placing them in
the Sectors table, and for each wedge W and each tile T that adds to or
subtracts from W, records the T->W in the Sectors2Tiles table (both positive
and negative parents). So, in Figure 3, the green wedge (the leftmost wedge)
would have tile A as a positive parent and tile B as a negative parent.
Boxes
A particular tiling run works on a set of (contiguous) staves, and indeed only
a section of each stave called a chunk. These areas are defined by disjoint
TilingRegions. To complicate matters, some TilingRegions have rectangular
holes in it them that represent bad seeing (bright stars, cosmic rays or other
flaws). So a tiling run looks something like Figure 5. And each
TilingGeometry is spherical rectangle with spherical-rectangular holes (see
Figure 5.)
 |
| Figure 5.Staves (convex sides not illustrated)
are processed in chunks. TilingGeometry is a
chunk/stavesubset with holes
(masks). TilingBoxes cover a
TilingGeometrywith disjoint spherical rectangles. There
are many such coverings, two are shown for TG1. The one at left has 23
TileBoxes while the one at right has 7
TileBoxes |
To simplify matters, we want to avoid the holes and work only with simple
convex regions. So we decompose each TileGeometry to a disjoint set of
TileBoxes. As Figure 5 shows, there are many different TileBox
decompositions. We want a TileBox decomposition with very few
TileBoxes. Fewer is better - but the answer will be the same in the end since
we will merge adjacent sectors if they have the same depth.
It is not immediately obvious how to construct the TileBoxes. Figure 6 gives
some idea.
First, the whole operation of subtracting out the masks happens inside the
larger TilingGeometry, called the Universe, U. We are going to construct
nibbles which are a disjunctive normal form of the blue area with at least one
negative hole edge to make sure we exclude the hole. These nibbles are
disjoint and cover the TileGeometry and exclude the mask (white) area.
As described in "There Goes the Neighborhood: Relational Algebra for Spatial
Data Search" we represent spherical polygons as a set of half-space
constraints of the form h = (hx,hy,hz,c). Point p = (px,py,pz) is inside
the halfspace if hx*px+hy*py+hz*pz>c. A convex region, C ={hi} is the set of
points inside each of the hi.
Given that representation we can compute the set N of nibbles covering region
R = U-C as follows:
Compute R = N = U - C where U and C are convex regions (C is the "hole" in U)
the idea is
R = {ui} - {ci}
= U &{~c1} | U&{~c2} | ...| U&{~cm}
= U&~c1 | U&c1&~c2 | ... | U&c1&c2&...&cm-1&~cm
The terms in the last equation are called nibbles.
They are disjoint (look at the terms if each term has a unique ~ci)
and together they cover R and exclude C (each ~ci excludes C).
Algorithm:
R= {} -- the disjoint regions will be added to R.
NewU = spRegionCopy U -- make a copy of U so we do not destroy it
for each c in C -- for each constraint in c that is an arc
-- of the hull
Nibble = NewU &{ ~c } -- intersect Not c with the current universe
if Nibble not empty -- if Not c intersects universe then
add Nibble to R -- Add this Nibble to answer set
NewU = NewU & {c} -- Not c is covered, so reduce the universe
When each positive TilingGeometry is "nibbled" by its masks, the resulting
nibbles are the TileBoxes we need.
The procedure spCreateTileBoxes creates, for each TilingGeometry, a set of
TilingBox regions that cover it. That procedure also records in Region2Boxes a
mapping of TilingGeometry-> TileBox so that we can tell which TilingGeometry
region covers a box.
SkyBoxes are the unification of all TileBoxes into a partitioning of the
entire sky. Logically, SkyBboxes are the Boolean combination of all the
TileBoxes - somewhat analogous to the relationship between wedges and tiles.
A SkyBoxes may be covered by multiple TilingGeometries (and have corresponding
tiling runs); Region2Boxes records this mapping of TilingGeometry -> TileBox.
Figure 7 illustrates how SkyBoxes are computed and how the TilingGeometry
relationship is maintained.
 |
| Figure 7. SkyBoxes are the intersection of
TileBoxes. A pair can produce up to 7
SkyBoxes. The green areas are covered by the union of
the tiling runs of the two TileBoxes and
the other SkyBoxes are covered by the Tiling Runs of
their one parent box.
|
spCreateSkyBoxes builds all the SkyBoxes and records the dependencies.
spCreateSkyBoxes uses the logic of spRegionQuradangleFourOtherBoxes to create
the SkyBoxes from the intersections of TileBoxes.
From Wedges and SkyBoxes to Sectorlets to Sectors
We really want the sectors, but it is easier to first compute wedges and
SkyBoxes and then build the sectors from them. Recall that:
Wedge: a Boolean combination of tiles.
Skybox: a convex region of the survey covered by certain TilingRuns.
So, the sectors are just
Wedge ( Skybox.
This is may be fine a partition - but two adjacent sectors computed in this
way might have the same list of covering TileGeometry and Tiles in which case
they should be unified into one sector. So, this first Wedge-SkyBox partition
is called sectorlets. These sectorlets need to be unified into sectors if they
have the same covering tiles. This unification gives us a unique answer
(remember that Figure 5 showed many different TileBox partitions, this final
step eliminates any "fake" partitions introduced by that step).
Sectorlets are computed as follows: Given a wedge W and a SkyBox SB, the area
is just W ( SB. If that area is non-empty then we need to compute the list of
covering tileGeometry and tiles. The TilingGeometries come from SB. The
tiles are a bit more complex. Let T be the set of tiles covering W. Discard
from T any tile not created by a tiling run covering SB. In mathematical
notation:
T(sectorlet) = { T e T(wedge) | ( TileRun TR covering SB and TR generated T}
T(sectorlet) is the tile list for the sectorlet W ( SB. This logic is
embodied in the procedure spSectorCreateSectorlets (note that wedges have
positive and negative tiles).
But, a particular tile or set of tiles can create many sectorlets. We want
the sector to be all the adjacent sectorlets with the same list of parent
tiles (note that sectorlets have positive (covering) and negative (excluded)
parents that make up the sector).
 |
| Figure 8.This diagram shows some SDSS data and demonstrates
the concepts of Tile, Mask,
TileBox, TilingGeometry,
SkyBox, Wedge, Sectorlet,
and Sector. |
The routine spSectorCreateSectors unifies all the sectorlets with the same
list of parent tiles into one region. This region may not be connected (masks
or tiling geometry may break it into pieces which we then glued back together
- see the example of 5 sectorlets creating one sector in Figure 8.)
All these routines are driven by the parent spSectorCreate routine.
|
