<> <> <<>> DIRECTORY Rope, IO, AlgebraClasses, BigRats, RatIntervals, VariableSequences, Polynomials, AlgebraicNumbers, Sequences, Formulas, SamplePoints, CoveringSets, Cells; QECadExtension: CEDAR DEFINITIONS ~ BEGIN OPEN AC: AlgebraClasses, BR: BigRats, RI: RatIntervals, AN: AlgebraicNumbers, SEQ: Sequences, POL: Polynomials, QFF: Formulas, SP: SamplePoints, CS: CoveringSets; <> <> <> <> <> RegionExtendCadToCad: PROC [cad: Cad]; <> <> <> <<1. MaximalSignedRegions[i-1, cad, TRUE]; regions _ ExtractSignedRegions[i-1, cad, TRUE]; sort regions in order of decreasing dimension (for i-1 = 2, put degenerate 0-dimensional regions after nondegenerate).>> <<2. cad.cells _ NIL; Go down sorted list of regions, for each:>> <<2a. currentCells _ ExtendRegionToCells[i, currentRegion, cad]; newAdjacencies _ NIL;>> <> <<2b. Do this step only if i = 2 or 3. If dimension of currentRegion < i-1, then determine adjacent regions of larger dimension. Sort these into order of increasing dimension. Go down this list, and for each region on it, find all cell-cell adjacencies between currentRegion and this region. Sort these adjacencies into decreasing sum of cell dimensions. For the next such adjacency, newAdjacencies _ AdjacenciesOverAdjacency[i, adjacency, cad]. If newAdjacencies = NIL, i.e. if needed auxiliary E^(i-1) cell-cell adjacencies, or non-NIL sample points, cannot be found, then go to the next cell-cell adjacency between current region and this region. If needed auxiliary adjacencies and/or non-NIL sample points cannot be found for any cell-cell adjacency between current region and this region, give up on building adjacencies in E^i between stacks over current region and this region. >> <> <<2c. Insert cells of currentCells into cad.cells in lexicographical order. IF newAdjacencies # NIL, then enter its adjacencies into the appropriate cells of cad.cells. >> <<3. If i-space cad.localizationFormula # NIL, then delete all cells of cad.cells which don't satisfy it, and all adjacencies involving those cells .>> <<4. For i = 1, 2 or 3, if no localization, we now have a graph for the cad of E^i in which a maximal signed regions computation will yield (signed) components (in 1 and 2-space, we can have all adjacencies, in 3-space, probably only a proper subset of all adjacencies.) >> ExtendRegionToCells: PROC [dimension: CARDINAL, region: SignedRegion, cad: Cad] RETURNS [newCells: SEQ.Sequence]; <> <> <<(Let i = dimension). Method: Evaluate polys at base sample point, irreducible basis of algebraic polys, isolate roots, construct extended sample points, eval gsfd of i-variate polynomial at endpoints of isolating interval, or i-variate polynomial itself at easy primitive sector sample point, when we want its sign.>> ExtendCellToStacks: PROC [i: CARDINAL, cell: Cells.Cell, cad: Cad] RETURNS [StacksInEi: SEQ.Sequence]; <> ExtendStacksToStacks: PROC [i: CARDINAL, StacksInEiM1: SEQ.Sequence, cad: Cad] RETURNS [StacksInEi: SEQ.Sequence]; <> <> <> END.