Algorithm Descriptions
Help
 Archive Intro
 Table Descriptions
 Schema Browser
 Glossary
 Algorithms
 Introduction to SQL
 Form Query User Guide
 Query Limits
 How To
 FAQ
 API
 sdssQA
 Download
 SkyServer Sites
 SkyServer Traffic Page
 Web Browsers
 Contact Help Desk

Creating Sectors

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, about 1.5 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 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.