summary |
shortlog |
changelog |
graph |
tags |
bookmarks |
branches |
files |
changeset |
file |
latest |
revisions |
annotate |
diff |
comparison |
raw |
help

include/geometry/NOTES

author | Dmitriy Morozov <morozov@cs.duke.edu> |

Mon, 25 Feb 2008 04:37:49 -0500 | |

branch | ar |

changeset 68 | 8f2610103946 |

parent 19 | efa14432761a |

permissions | -rw-r--r-- |

Initial commit of KineticSort-based ARVineyard
Compiles, but needs to be runtime debugged.

== 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.