Osculating ellipsoids

Let K be a given smooth, origin-symmetric, strictly convex body in n dimensional euclidean space. At every point x on the boundary of K there exists an origin-symmetric ellipsoid Ex that touches x of second-order, the osculating ellipsoid at x. Denote the family of osculating ellipsoids by F:={Ex:x∈boundary of K}. Moreover, set G:={TE:E∈F & T∈SL(n)}. Is it true … Read more

In search for isotropic graphs: Straight lines and parallels

I wonder why I can find only so little attempts of concisely defining “directions” and “isotropy” of graphs. In Euclidean spaces “directions” can be identified with equivalence classes of parallel straight lines. And on directions definitions of “isotropy” and “anisotropy” normally rely. I believe it’s easy to define a “straight line” in a graph: Definition … Read more

Nontrivial lower bounds on Cheeger inequalities for Markov chains

For a reversible Markov chain Xt on Rn with transition kernel K and stationary distribution π, it is well-known that the `spectral gap’ (basically, the size of K when restricted to functions orthogonal to π) of K can be estimated roughly by the following Cheeger constant: Φ=inf where \Phi(S) = \frac{\int_{S} K(x,S^{c})dx}{\pi(S)} – see e.g. … Read more

Maximin diameter of a transformed convex figure

You are given a compact convex figure in the plane, $C$. Your goal is to transform $C$ to a different figure $C’$ with the smallest possible diameter, as long as: The trasformation from $C$ to $C’$ is affine and invertible (e.g. scaling in one or more directions); $C’$ contains a disc with diameter $1$. For … Read more

Unit triangles with vertices on circles

Characterize all triples c_1,c_2,c_3 of circles in the plane such that there are infinitely many unit regular triangles a_1a_2a_3 with a_i\in c_i for i=1,2,3. In particular, are there any triples having this property and such that the circles are neither congruent (i.e. have equal radii) nor concentric? I wonder whether there is an elegant approach … Read more

Finding integer points on an N-d convex hull

Suppose we have a convex hull computed as the solution to a linear programming problem (via whatever method you want). Given this convex hull (and the inequalities that formed the convex hull) is there a fast way to compute the integer points on the surface of the convex hull? Or is the problem NP? There … Read more

Isostatic graphs and the Henneberg conjecture

I have been reading “Combinatorial Rigidity” by Graver, Servatius and Servatius and I am interested in their chapter on rigidity in dimension ≥ 3. I have two questions. What is the current status of the Henneberg conjecture (ie that every 2-extension of a 3-isostatic graph is isostatic?) The GSS book was published in ’91. Is … Read more

Affine hull of a set of non-negative matrices with fixed row-sums

Fix any non-negative matrix M∈Rm×n≥0 that contains no zero-row and no zero-column. Further, fix any positive vector r∈Rm>0. With nz(M):={(i,j) | Mi,j>0} the index set of non-zero-entries in M, and 1 the all-ones-vector, define the set Sr,W:={A∈Rm×n≥0 | A1=r, nz(A)⊆nz(M)} of all non-negative matrices that have row sum r at that have at least the zero-entries of M, that is … Read more

Finding smallest ellipsoid that circumscribes over intersection of two ellipsoids that do not have common center

Does this already exist in literature? The closest Ive been able to find is circumscribe intersection of two ellipsoids with a common center by W. Kahan (http://www.cs.berkeley.edu/~wkahan/Ellipint.pdf). I am looking for a method to circumscribe an ellipsoid over the intersection of two ellipsoids. The ellipsoid do not have a common center. PS: We can assume … Read more

How to efficiently compute the generalized cross product?

It’s possible to extend the well known cross product between two vectors in \mathbb{R}^3 to n-1 vectors in \mathbb{R}^n. Let \vec{v_1}, \vec{v_2}, \dots, \vec{v}_{n-1} \in \mathbb{R}^n and \vec{e}_1 = (1, 0, 0, \dots, 0)^T, \vec{e}_2 = (0, 1, 0, \dots, 0)^T, \dots, \vec{e}_n = (0, 0, \dots, 0, 1)^T be the unit vectors of the … Read more