== Predicates/Constructions

  * circumsphere, side of circumsphere

  * barycentric coordinates

  * degenerate simplex

  * projection on a k-flat, squared distance to the k-flat

  * signed square distance to an oriented (d-1)-flat (?)

== Computing circumcenter and circumradius of a k-simplex in d dimensions.

  * Ken Clarkson's Gram-Schmidt-based algorithm works perfectly over any field. 

    The idea is as follows. 

    Given points p_i, the circumcenter c satisfies (p_i-c)^2 = r^2.  By

    translation, we can assume that some p_i is at the origin, so that c^c=r^2,

    and that equation becomes p_i \cdot c - p_i^2/2 = 0.  That is, [c -1/2] is

    normal to [p_i p_i^2].  Also, c must be an affine combination of the p_i,

    so if we start with a point [c' 0] with c' in the affine hull of the p_i,

    and remove all multiples of all [p_i p_i^2] from it, via Gram-Schmidt for

    example, and then scale the result so that the last entry is -1/2, we get

    c (alternatively we can start with [0 1]). Note that if the simplex is 

    degenerate (its affine hull is less than k-dimensional), the last entry of 

    c is 0.

      P = {p_0, ..., p_k}

      p'_i = p_i - p_0                  # make p_0 the origin

      p''_i = [p'_i p'_i^2]             # lift the points

      c' = 0                            # c is in the affine hull of p'_i

      c'' = [c' 1]                      # c'' is not in the affine hull of p'_i^2

      for i = 1 to k:                   # create an orthogonal basis for aff(p''_i)

        a''_i = p''_i

        for j = k-1 downto 1:

          a''_i -= a''_j * (a''_i \cdot c''_j)/c''_j^2

      for i = 1 to k:

        c'' -= a''_i * (c'' \cdot a''_i) / (a''_i^2)

      c' = c''[1..d]/(-2 * c''[d+1])    # scale c'' down

  * Ulfar Erlingsson's, Erich Kaltofen's and David Musser's "Generic 

    Gram-Schmidt Orthogonalization by Exact Division" (ISSAC'96) gives an 

    algorithm to compute Gram-Schmidt for vector space with integral domain 

    coefficients. I need to understand the paper better to see the advantages 

    over normalizing rationals at every step of the computation above 

    (the paper's introduction says that it avoids "costly GCD computations").

  * Using QR decomposition (or any other orthogonal decomposition), and 

    then using the formula of the circumsphere on the matrix R (which is 

    just the simplex rotated into a k-dimensional space):

    * Only (d-2) determinants of a k by k matrix are required which is nice.

    * All (implemented) computation of the QR decomposition that I have found 

      so far requires square roots (for norms), divisions, and often

      comparisons.  While divisions are acceptable, square roots and

      comparisons aren't.

    * There is a string of papers in late 80s, early 90s on square root free 

      and division free algorithms for QR decomposition out of VLSI community.

      There is a paper that claims to put all such techniques into one

      framework. There is also a paper that says that all such techniques don't

      work, and square root implementation needs to be reconsidered.  (authors

      to look up if searching for these papers are K.J.R. Liu and E.

      Frantzeskakis)

  * Using the formulas from Herbert's Weighted Alpha Shapes paper which are 

    derived from formulas of the planes that are lifted Voronoi cells. This 

    approach requires (d-k)*(d+2) determinants of k by k matrices, which is not 

    great.