User joseph o'rourke - MathOverflow

Answer by Joseph O'Rourke for How can I randomly draw an ensemble of unit vectors that sum to zero?

2013-05-20T02:14:06Z

Here is one approach. Start with a regular $n$-gon in the $xy$-plane with unit edge lengths; say its vertices are $v_i$, $i=0,\ldots,n-1$. Now iterate the following process.

Select a random diagonal, $v_i v_j$. Rotate the chain $v_i, v_{i+1}, \ldots, v_j$ (indices appropriately mod $n$) as a rigid unit about the line through $v_i v_j$, by a random angle $\theta \in [0,2\pi)$.

Continue until there is sufficient "mixing." I illustrate the process below for 30 iterations applies to a hexagon.

(Apologies for the scale—the chain wanders away from its initial locaion.)

Answer by Joseph O'Rourke for Trilateration problem

2013-05-16T11:51:12Z

For fixed $P_i$, $P_{i+1}$, the apex $O$ of the triangle with base $P_i P_{i+1}$ follows an algebraic curve as a function of your unknown scale factor $k$:

You could intersect these curves in pairs and average the intersection points. In your example, intersect the curve for $P_1 P_2$ with the curve for $P_3 P_4$.

Answer by Joseph O'Rourke for How to find overlap between two convex hulls,along with the overlap area

2013-05-14T18:26:17Z

If you care about speed, then there is a linear-time algorithm specifically tuned to intersecting two convex polygons, described in the book, Computational Geometry in C, with downloadable code.

(I took the above snapshot from an illegal scan of the book!)

Answer by Joseph O'Rourke for Applications of visual calculus

2013-05-12T22:15:09Z

Perhaps this previous MO question may help: Taking “Zooming in on a point of a graph” seriously, e.g., this answer link.

Answer by Joseph O'Rourke for Inferring the properties of a visibility blocker tangential to a point-like light source

2013-05-12T00:23:07Z

If I have interpreted your situation correctly, all you can learn from your center of gravities $C_L$ is the angular aperture of $P$ at the origin (from any one $L$), and the orthogonal to the extremes of $P$ (from a sequence of $L$s):

In $\mathbb{R}^3$, you could not distinguish between a vertical and a horizontal segment $P$ (or a thickened segment $P$).

Optimal inspection path on a sphere

2013-05-10T12:14:15Z

Suppose you would like to "inspect" every point of a unit-radius sphere $S \subset \mathbb{R}^3$ by walking along a path $\gamma$ on $S$, but you can only see a distance $d$ from where you stand.

Q1. For a given $d \in (0,\pi]$, what are the shortest such paths $\gamma(d)$?

Two other ways to define $\gamma(d)$:

The shortest path $\gamma$ such that every point on $S$ is no more than a distance $d$ from some point of $\gamma$.
The shortest path $\gamma$ such that the union of disks of radius $d$ centered on every point of $\gamma$ cover $S$.

For $d \in [\pi/2,\pi]$, $\gamma(d)$ is an arc of a great circle of length $2\pi - 2d$. So, for $d=\pi$, $\gamma$ is a single point; for $d=3\pi/4$, $\gamma$ is an arc of length $\pi/2$; for $d=\pi/2$, $\gamma$ is a semicircle. As $d$ approaches zero, it seems that $\gamma$ should be some type of spiral, e.g.:

           _{(Image from grabcad.com.)}
What is quite unclear to me is when $d$ is less than but close to $\pi/2$. For example, suppose $d = \frac{5}{12}\pi = 75^\circ$. The union of disks of this radius centered on the equatorial semicircle that works for $\pi/2$ is shown in (a) below: a strip connecting the north and south poles is uncovered (blue circles are boundaries of disks of radius $d$ centered on $\gamma$):

One can construct a candidate $\gamma$ as in (b) above: extend the semicircle at each end so that all points on the equator are reached, and add short vertical sections, red to reach the north pole, and green to reach the south pole. It does not seem likely that such sharp turns yield the shortest $\gamma$.

Perhaps this question can be answered even without precise understanding of $\gamma(d)$ for all $d$:

Q2. Does $\gamma(d)$ vary continuously with respect to $d$?

I originally wanted to explore this for any (smooth, closed, compact) surface in $\mathbb{R}^3$, but it already seems not so straightforward for the sphere.

Q3. Has this question been studied before? It feels classical.

The question could also be posed for $(d{-}1)$-dimensional spheres in $\mathbb{R}^d$, again seeking an optimal inspection path for each $d$. (My interest in $\mathbb{R}^3$ stems from two related concepts: Voronoi diagrams on a surface, and the cut locus with respect to a path, although neither seems to help here.) Thanks for any pointers or ideas!

(Related earlier MO questions: Optimal paintbrush geodesics; Shortest closed curve to inspect a sphere.)

Answer by Joseph O'Rourke for Straight Line Passing Through a Convex Region

2013-05-10T15:01:04Z

It so happens that Wikipedia contains an article entitled, "Intersection of a polyhedron with a line," but I doubt that answers your question.

A better answer is provided by another MO question, "Intersection points of straight line segment with Voronoi diagram": You can achieve $O(\log n)$ query time but only if you invest quadratic time preprocessing (which corroborates Ricky Demer's comment).

Answer by Joseph O'Rourke for Modern Mathematical Achievements Accessible to Undergraduates

2013-05-05T20:00:30Z

It is not difficult to think of examples where the content, statement, and import of a result are accessible, but the proof is not accessible. Hales' resolution of the sphere-packing Kepler conjecture can certainly be appreciated, and the proof outline and technique are accessible, but it would be a stretch to say that the proof is "accessible to undergraduates" (or to anyone, for that matter!).

I have had some success explaining to undergraduates the proof of the Bellows Conjecture: that the volume of any flexible polyhedron is constant (and so cannot serve as a bellows). The 1995 proof by Idzhad Sabitov (for genus-zero polyhedra) uses a grand generalization of Francesca's 15th-century formula for the volume of a tetrahedron as a function of its six edge lengths. Sabitov showed that the volume of a polyhedron can be expressed as a root of a polynomial whose coefficients are polynomials in its edge lengths, a remarkable result. (The polynomial is already degree-16 for an octahedron.) Because the edge lengths of a flexing polyhedron are constant, the polynomial is fixed and can only change discretely by jumping from one root to another. But this contradicts what should be a continuous volume change under a continuous flex.

_{Steffen's 14-triangle, 9-vertex flexible polyhedron (Fig.23.9 in Geometric Folding Algorithms).}

Optimal paintbrush geodesics

2013-05-05T15:04:48Z

Let $S$ be a smooth, closed surface in $\mathbb{R}^3$, and $\gamma$ a geodesic segment on $S$, i.e., a finite-length piece of a geodesic. Define $\gamma(w)$ as all the points of $S$ within a distance $w$ of $\gamma$: all the $x \in S$ such that the shortest distance on $S$ from $x$ to $\gamma$ is at most $w$. One can imagine $\gamma(w)$ representing the path of a paintbrush of width $2w$ as it traces $\gamma$:

_{(Image based on one at rdrop.com.)}

Q1. For a given $S$, which $\gamma(w)$ have the properties that (a) all of $S$ is covered by $\gamma(w)$, and (b) the area product $\;|\gamma| \cdot w$ is minimized, where $|\gamma|$ is the length of $\gamma$.

In some sense, this is an optimal paint path: a paintbrush tracing $\gamma$ and spreading paint $\pm w$ covers the surface most efficiently. For example, for $S$ a unit-radius sphere, it seems that $\gamma$ a half-great circle, $|\gamma| = \pi$ is optimal with $w=\pi/2$, area product $\frac{1}{2} \pi^2$.

Q2. Is the semi-great circle indeed optimal for the sphere?

Q3. Are there other clear examples of optimal paintbrush geodesics?

Q4. Has this notion been studied before, perhaps in another guise?

Thanks for ideas/pointers!

Answer by Joseph O'Rourke for Intersection points of straight line segment with Voronoi diagram

2013-05-03T19:26:30Z

The paper by Chazelle and Liu,

"Lower bounds for intersection searching and fractional cascading in higher dimension." 2001. (ACM link)

shows that for planar convex subdivisions, the answer is Yes, there is a computationally efficient method if you allow quadratic storage, but No if you insist on subquadratic storage:

Your one hope is that, because a Voronoi diagram is a special convex subdivision, this result can be improved by exploiting its Voronoi-ness.

Random rings linked into one component?

2013-04-27T17:56:13Z

Let $S$ be a sphere of unit radius. Let $C_n$ be a collection of unit-radius circles/rings whose centers are (uniformly distributed) random points in $S$, and which are oriented (tilted) randomly (again, uniformly).

Q1. As $n \to \infty$, does the probability that all the rings in $C_n$ are linked together in one component approach $1$?

By "linked together" I mean that if you pick up any one ring, all the others are physically connected and would follow. For example, below there are $n=5$ rings, four of which are connected, but one (topmost) is not:

Q2. Same as Q1, but with $S$ a sphere of some (perhaps large) radius $r > 1$.

Q3. Same as Q1, except with $S$ an arbitrary convex body, e.g., a cube.

I feel the answer to Q1 should be Yes, but I am less certain of Q3. Exact computation of probabilities as a function of $n$ might be difficult, but I am hoping there are relatively simple arguments to settle these questions. Thanks for ideas!

Answered (1May13). The combination of Ori Gurel-Gurevich's and Benoît Kloeckner's postings constitute a rather complete answer, establishing that the answer to all my question is Yes, even without the assumption that $S$ is convex. Thanks for the interest!

Answer by Joseph O'Rourke for Intersection of 2 visibility polygons

2013-04-30T11:58:13Z

Here is an argument, a revision (and replacement) of one I sketched earlier.

Let $p_1$ and $p_2$ both see $a$ and $b$. I claim that every point along the shortest path $\sigma$ connecting $a$ to $b$ inside $P$ is visible to both $p_1$ and $p_2$. With this claim established, we know the intersection of the visibility polygons is connected.

Start turning/sweeping the rays $p_1 a$ and $p_2 a$ counterclockwise along $\sigma$ toward $b$, simultaneously tracking the same point along $\sigma$. If both rays remain unobstructed throughout the sweep, we are finished. So suppose otherwise. Then one or the other ray, say $p_2 a$, must encounter an obstruction, a reflex vertex $v$ hitting $p_2 a$, blocking the visibility to point $x \in \sigma$. Then we have some exterior points of the polygon enclosed within the closed path $p_2 x \cup \sigma(x,b) \cup b p_2$ of points interior to $P$, contradicting the simplicity of the polygon, i.e., the polygon has a hole:

Can every $\mathbb{Z}^2$ disk be pinball-reached?

2013-04-20T01:03:31Z

Let every point of $\mathbb{Z}^2$ be surrounded by a mirrored disk of radius $r < \frac{1}{2}$, except leave the origin $(0,0)$ unoccupied by a disk.

Q. Is it the case that every disk can be hit by a lightray emanating from the origin and reflecting off the mirrored disks?

Lightrays are composed of (infinitely thin) segments, and reflect off the disks with angle of incidence equal to angle of reflection. For example, here is one way (of many ways) to hit the $(0,2)$ disk when $r = \frac{1}{4}$ with two reflections; it clearly cannot be reached directly, with zero reflections:

I believe the answer to my question Q is Yes, but I would be grateful for confirmation from the dynamical systems experts. (Forgive me if I have not learned sufficently from my previous, related question, "Pinball on the infinite plane.")

It occurs to me it might be interesting to color the disks according to the minimum number of reflections needed to hit each...

Answer by Joseph O'Rourke for Can every $\mathbb{Z}^2$ disk be pinball-reached?

2013-04-28T00:20:46Z

I add this image just to illustrate that matters seem more complicated (as Douglas Zare has emphasized) when the radii of the disks approaches $\frac{1}{2}$:

Answer by Joseph O'Rourke for Incidences of quadratic forms and points

2013-04-27T00:05:18Z

Your terse question leaves many possible interpretations, and forgive me if this is a misinterpretation. The 2012 paper by Micha Sharir, Adam Sheffer, and Joshua Zahl,

"Incidences between points and non-coplanar circles." arXiv:1208.0053 (math.CO)

showed that the number of incidences between $m$ points and $n$ arbitrary circles in three dimensions—in the situation when the circles are "truly three-dimensional," in the sense that there exists a $q < n$ so that no sphere or plane contains more than $q$ of the circles—then the number of incidences is

$$O^*\big(m^{3/7}n^{6/7} + m^{2/3}n^{1/2}q^{1/6} + m^{6/11}n^{15/22}q^{3/22} + m + n\big).$$

The complexity of this result illustrates the complexity of the topic!

_{(Figure from Boris Aronov, Vladlen Koltun, Micha Sharir, "Incidences between Points and Circles in Three and Higher Dimensions,"
Discrete & Computational Geometry.
February 2005, Volume 33, Issue 2, pp 185-206. (Springer link).)}

Answer by Joseph O'Rourke for weighted graph plot

2013-04-26T16:20:53Z

Almost every advanced graph drawing package has implemented one or more force-directed layout algorithms, which almost all permit adjustments to the repulsion by edge weights. One is Gephi, which permits one to alter the layout parameters interactively:

_{(Image from this link.)}

Answer by Joseph O'Rourke for Secondary Polytope Simplicial?

2013-04-24T00:12:00Z

To echo André, it would be useful to see a definition of what you mean. The secondary polytope is generally defined for a point configuration, not for a polytope. Here are two definitions, the first from Carl Lee's article "Subdivisions and triangulations of polytopes" (Handbook of Discrete and Computational Geometry), and the second from Sven Herrmann's paper, "On the facets of the secondary polytope" (arXiv.0908.2737v3). In the first, $V$ is a set of points in $\mathbb{R}^d$, in the second, $\cal{A}$ is a multiset of points in $\mathbb{R}^d$.

Each vertex of the secondary polytope corresponds to a triangulation of the point set.

So perhaps you are asking for the secondary polytope of a point set whose convex hull is a simplicial polytope? But that can't be what you mean: a convex polygon is a simplicial polytope in $\mathbb{R}^2$ (its facets are segments, 1D simplicies), and the secondary polytope of a hexagon is not simplicial: its facets are quadrilaterals and pentagons.

_{(Image from Discrete and Computational Geometry)}

Answer by Joseph O'Rourke for "Trapping" of discs after random sequential adsorption

2013-04-21T00:31:14Z

This is not an knowledgeable answer, so forgive me if this is irrelevant.

The paper, "Random sequential adsorption," by Jens Feder (Elsevier link), seems to indicate that "the size distribution for non-overlapping holes" is known, which, at least superficially, seems to relate to the quantity you want to compute...?

Abstract. By placing at random disks onto a surface, but adsorbing only those that do not overlap previously adsorbed disks, one will finally reach the jamming limit beyond which no more disks can be adsorbed. We find, using computer simulations, that the coverage at the jamming limit is θ = 0·547 ± 0·002 for disks and θ = 0·562 ± 0·002 for aligned squares. For the jammed state we have evaluated the pair correlation function for the disks and the size distribution for non-overlapping holes. [...]

Surfaces filled densely by a geodesic

2013-04-14T13:02:43Z

Which smooth, closed surfaces $S \subset \mathbb{R}^3$ have no single geodesic $\gamma$ that fills $S$ densely?

Say a geodesic $\gamma$ "fills $S$ densely" if the closure of the set of points through which $\gamma$ passes equals $S$. Some examples:

A sphere: every geodesic is a great circle.
Zoll surfaces, as discussed here: "Surfaces all of whose geodesics are both closed and simple."
An ellipsoid.

(Image from GeographicLib.)
A torus generally has many geodesics that fill the surface.

(Image by John Oprea)

My assumption is that almost all surfaces have geodesics that fill them. Is this known, under any interpretation of "almost all"? I would also be interested in extending the list of exceptional surfaces beyond {sphere, Zoll, ellipsoid}. Thanks for pointers!

Answers Summary (18Apr2013):

(Robert Bryant, Mikhail Katz) Any surface of revolution with poles has no dense geodesic. This holds for convex or nonconvex surfaces of revolution.
(Robert Bryant) There are generalizations of Liouville surfaces (due to Goryachev-Chaplygin and to Dullin-Matveev) that have no dense geodesic.
(Misha Kapovich) Every surface may be perturbed by gluing on "focusing caps" so that it has dense geodesics.
(Keith Burns) Guess: There is always a dense geodesic on a closed Riemannian surface of genus $\ge 2$.

Answer by Joseph O'Rourke for Lecture on Fractals for Middle School Students

2013-04-19T16:24:45Z

Your task is both a challenge and an opportunity: they will be unfamiliar with complex numbers, but perhaps you could motivate the utility of complex numbers. I might try to introduce them to the computation of a Julia set, at first entirely computationally, showing them how $z$ grows under repeated computation of znew = zold² + c, all in terms of coordinates and distance from the origin (without mentioning complex numbers). They need not know any programming language to understand a simple iterative loop. Once they see how some starting points $z$ scoot off to infinity, and others hang around the origin, they can appreciate it would be natural to color each point according to its scooting-to-$\infty$ speed. And then they could understand how to make a Julia set:

_{(Image from cgtutor)}

With this understanding secured, you might be able to introduce complex numbers.

For motivating applications, you could easily connect to the use of fractals in computer graphics in movies (Lord of the Rings; The Hobbit, etc.):

_{(Image from LifeInWireframe)}

Answer by Joseph O'Rourke for Nash Embedding Theorems for Pseudo-Riemannian Manifolds?

2013-04-16T23:53:36Z

Not clear where you are headed with your concise question, but if you have any interest in Lorenzian manifolds as instances of pseudo-Riemannian manifolds, then this might be of interest, especially for the theorem of Campbell:

"The embedding of General Relativity in five dimensions." Carlos Romero, Reza Tavakol, Roustam Zalaletdinov. General Relativity and Gravitation. March 1996, Volume 28, Issue 3, pp 365-376. (Springer link.)

Abstract. We argue that General Relativistic solutions can always be locally embedded in Ricci-flat 5-dimensional spaces. This is a direct consequence of a theorem of Campbell (given here for both a timelike and spacelike extra dimension, together with a special case of this theorem) which guarantees that any $n$-dimensional Riemannian manifold can be locally embedded in an $(n+1)$-dimensional Ricci-flat Riemannian manifold. [...]

And there are many papers in some sense following, e.g.: "The embedding of space–times in five dimensions with nondegenerate Ricci tensor," F. Dahia and C. Romero, J. Math. Phys. 43, 3097 (2002). (AIP link.)

Answer by Joseph O'Rourke for How many vertices can a convex polytope have?

2013-04-13T00:07:15Z

What you call $n$ in your posting is often called $d$ in the literature, but I will stick with your notation. So $n$ is the dimension. Let $V$ be the number of vertices, and $k$ the number of facets. Then $V = \Theta( k ^ {\lfloor n/2 \rfloor} )$. More precisely, the maximum $V$ is given by McMullen's Upper Bound Theorem, realized by duals of cyclic polytopes. Cyclic polytopes maximize the number of facets for a fixed number of vertices, so their duals maximize the number of vertices for a fixed number of facets.

See, e.g.,

"Basic Properties Of Convex Polytopes." Martin Henk, Jürgen Richter-Gebert, and Günter M. Ziegler. Handbook of Discrete and Computational Geometry, Chapter 16. CRC Press. 2004. (CiteSeer link)

Answer by Joseph O'Rourke for Convex representation of (planar) graphs

2013-04-12T00:03:48Z

Although what constitutes a "practical justification" is in the eye of the beholder, I would think this might qualify.

There is a notion called geometric routing that is used to solve network routing problems. The idea is to map the true GPS coordinates of a planar network on to a differently embedded network that supports fast and efficient routing. One such is greedy routing, which as its name implies, is an especially simple algorithm. There has been a conjecture that there exists a convex embedding which supports greedy routing. This has been proved, but only by losing another nice property, "succintness" (bits per vertex coordinate). Others have retained succinctness by changing the metric and using a convex embedding.

These complex details aside, the point is that convex embeddings of planar graphs are used as a basis for network routing algorithms. You could start with this paper, published just a month ago or so, and trace through its references:

He, Zhang. "A simple routing algorithm based on Schnyder coordinates." Theoretical Computer Science. February 2013. (Elsevier link)

Answer by Joseph O'Rourke for Separation of Anti-Hole Inequality

2013-04-11T12:41:57Z

Here is one reference, a 2010 book that may lead to other literature: Polyhedral and Semidefinite Programming Methods in Combinatorial Optimization, by Levent Tunçel:

Answer by Joseph O'Rourke for Constrained Triangulation of a Convex Polytope

2013-04-09T16:36:40Z

Once you have pre-specified some simplices $S$ that must be included in your triangulation of the convex polytope $P$, what remains is the problem of triangulating a nonconvex region: $P \setminus S$. There are nonconvex polyhedra (in dimension 3) that cannot be triangulated. I believe one could make such an example from the Schönhardt polyhedron, by insisting on the inclusion of three tetrahedra ($S$) external to that polyhedron as part of a triangulation of the convex hull ($P$) of two twisted triangles in parallel planes, so that $P \setminus S$ is the un-tetrahedralizable Schönhardt polyhedron (see below). And it is an NP-complete problem to decide if a given nonconvex polyhedron can be triangulated, a 1992 result of Ruppert and Seidel.

_{(Image from Wikipedia)}

If you want to nevertheless hope that your region can be triangulated, you might explore geometric bistellar flips to underlie an approach.

Rational points on a sphere in $\mathbb{R}^d$

2013-03-22T01:34:24Z

Call a point of $\mathbb{R}^d$ rational if all its $d$ coordinates are rational numbers.

Q1. Is the unit sphere $S :\; x_1^2 +\cdots+ x_d^2 = 1$ dense in rational points, i.e., does $S$ include a dense set of rational points?

This is certainly true for $d=2$, rational points on the unit circle.

Q2. If (as I suspect) the answer to Q1 is Yes, is there a sense in which the rational coordinates are becoming arithmetically more complicated with larger $d$, say in terms of their height?

If $x= a/b$ is a rational number in lowest terms (i.e., gcd$(a,b)=1$), then the height of $x$ is $\max \lbrace |a|,|b| \rbrace$.

This is far from my expertise. No doubt this is known, in which case a pointer would suffice. Thanks!

(Added, 22Mar13). I just found this reference. [Earlier misleading remark removed.]

Klee, Victor, and Stan Wagon. Old and new unsolved problems in plane geometry and number theory. No. 11. Mathematical Association of America, 1996. p.135.

Combinatorial distance between simplicial complexes

2013-04-04T23:50:46Z

Let $K_1$ and $K_2$ be two simplicial complexes. I am seeking a measure of the distance between $K_1$ and $K_2$ when viewed as combinatorial objects. What I have in mind is something like this.

Remove simplices (of various dimensions) from $K_1$ such that, at each stage, the remaining object is a simplicial complex. Then add simplices, again always remaining a simplicial complex, until a complex isomorphic to $K_2$ is obtained. The fewest number of simplices added or removed in order to "renovate" $K_1$ to $K_2$ is some measure of their distance. Perhaps, in order to accommodate the different dimensions, a simplex of dimension $d$ should have weight $d+1$ in the count. Let us call this the renovation distance between $K_1$ and $K_2$.

For example, below, removal of two triangles from $K_1$, and adding a triangle and a segment, reaches $K_2$ (with the isomorphism mapping indicated by the vertex labels) (Example corrected 5Apr13 by Vidit Nanda comment):

So here the renovation distance is at most $11$ (and I don't see a more efficient path). Likely it is not computationally easy to compute this renovation distance. (Update 5Apr13: Vidit Nanda observes that a special case is subgraph isomorphism, an NP-complete problem.)

My definition is not well-grounded in any theory. Have there been definitions of distances between simplicial complexes that capture a similar intuitive notion? I'd appreciate pointers to relevant literature. Thanks!

Uppercase Point Labels in High-School Diagrams: from Euclid?

2010-06-19T16:15:46Z

I wonder if the convention of labeling points in geometric diagrams with uppercase symbols ultimately derives from Greek mathematics, which was originally written in "majuscule" (uppercase) Greek script (in contrast to the "minuscule" script that was introduced much later (9th century?)). Certainly Euclid and Archimedes used only uppercase, and all of Descartes diagrams in La Geometrie (1637) follow the same convention.

It seems that middle- and high-school textbooks continue to use uppercase labels (is this only in the U.S.?), but college texts do not follow this as rigidly. This was brought home to me when I wrote a chapter for high-school teachers and the editors changed all my lowercase vertex labels to uppercase. I much prefer lowercase for point labels, although I do not quite know why I have this preference. (Maybe because uppercase seems like SHOUTING?) But when writing for an audience accustomed to a particular convention, it seems prudent to follow that convention.

My questions are: (1) Is the Greek majuscule script the origin of the uppercase diagram-labeling convention? (2) In so far as I am correct that the uppercase convention is followed up to high school but dissolves at more advanced levels, why does it persist to one level but dissolve beyond?

Is there a midsphere theorem for 4-polytopes?

2011-05-21T20:44:44Z

The (remarkable) midsphere theorem says that each combinatorial type of convex polyhedron may be realized by one all of whose edges are tangent to a sphere (and the realization is unique if the center of gravity is specified).

Q1. Is there an analogous theorem for 4-polytopes, that each combinatorial type may be realized by a polytope with ridges (or edges?) tangent to a 3-sphere?

Because the proofs of the midsphere theorem rely on the Koebe–Andreev–Thurston circle-packing theorem, a related query is:

Q2. Is there a generalization of the circle-packing theorem to sphere-packing?

Both questions may be generalized to arbitrary dimension.

I suspect the answer to both questions may be No, in which case a pointer would suffice. Thanks!

Symmetric dominance regions surrounding a Gaussian prime

2013-03-31T02:48:02Z

Let $z=a + b i$ be a complex number which is a Gaussian prime, on neither the $x$- nor the $y$-axis. So $a^2+b^2$ is a prime. Construct a region $D(z)$ surrounding $z$ which is the largest orthogonally convex polygon surrounding $z$ that is empty of Gaussian primes. ($D$ for Dominance.) More precisely, define $D(z)$ as the union of rectangles $R$ that (a) strictly include $z$, but (b) are empty of other Gaussian primes in the interior of $R$. Two examples are shown below: $z=1+i$, and $z=4+5i$, where the marked points on the boundary of $D(z)$ are Gaussian primes:

It seems likely that $D(z)$ is not well-defined, based on a comment of François Brunault to an earlier MO question, "Gaussian prime spirals":

it's unknown whether there are infinitely many Gaussian primes of the form $n+i$ with $n \in \mathbb{Z}$.

Nevertheless, I wonder if this question might avoid running into an unsolved problem:

Q. Is there a $z=a + b i$, with $a \neq 0$ and $b \neq 0$, such that $D(z)$ is symmetric about both a vertical line through $z$ and a horizontal line through $z$?

In the examples above, although $D(1+i)$ is a square, it is not symmetric about $1+i$. And $D(4+5 i)$ is symmetric about a horizontal through $z$ but not a vertical.

My guess is that the answer to Q is Yes, but I just haven't found the $z$ that leads to symmetry. My question can be answered by a single example. I am seeking some (minimal) structure to the distribution of the Gaussian primes. Thanks for thoughts/ideas!

Comment by Joseph O'Rourke

2013-05-21T17:47:02Z

I cannot access this paper at the moment, but its title suggests it might be relevant for the hexagonal trefoil: J. A. Calvo, The embedding space of hexagonal knots, Topolo. Appl. 112(2) (2001) 137–174.

Comment by Joseph O'Rourke

2013-05-20T02:27:44Z

@Alekk: Sorry, I cannot even guess. Perhaps others can...

Comment by Joseph O'Rourke

2013-05-16T23:42:35Z

Perhaps you are already familiar with the notion of a fat triangulation, in which the circum-to-inradius ratio of each simplex is bounded by a constant. Fat triangulations are candidates for your type of regularity. (And note that "regular triangulations" are yet a different concept.)

Comment by Joseph O'Rourke

2013-05-14T18:46:40Z

@meij: Yes! But of course that is the usual result of the convex hull computation.

Comment by Joseph O'Rourke

2013-05-13T16:25:46Z

Ah, then I have misinterpreted the question---missed that the concern is with the subset of $P$ corresponding to $E(v)$. So the answer is in fact Yes.

Comment by Joseph O'Rourke

2013-05-12T13:16:33Z

@Lesser: I don't see that. Are not the spheres cocentric? That's what I assumed. Of course, if you both increase the radius and move the sphere centers around, yes, you can learn more about $P$, even when it is convex.

Comment by Joseph O'Rourke

2013-05-12T00:54:48Z

The title of your question ("non-convex") does not match the question itself. Perhaps you are seeking a definition of a polytopal complex? This is defined in Ziegler's Lectures on Polytopes.

Comment by Joseph O'Rourke

2013-05-11T23:38:42Z

Is this a correct interpretation? The "detector" is the entire sphere of radius $L$. It only reports the centroid as a point in $\mathbb{R}^3$, inside the sphere, of all the radiation it receives.

Comment by Joseph O'Rourke

2013-05-10T16:38:30Z

@Gerhard: Or, because I am seeking a path rather than a tree, a Traveling Salesman open path visiting centers of a disk cover...

Comment by Joseph O'Rourke

2013-05-07T11:51:42Z

"It is straightforward to compute the connected components of a graph in linear time": en.wikipedia.org/wiki/…

Comment by Joseph O'Rourke

2013-05-07T01:41:34Z

Thank you for the correction!

Comment by Joseph O'Rourke

2013-05-05T16:50:50Z

@Will: Yes, I think so! Which is why this concept has not been studied---It's essentially empty. :-)

Comment by Joseph O'Rourke

2013-05-05T16:36:48Z

@Sergei: Ah, very nice!

Comment by Joseph O'Rourke

2013-05-05T02:15:11Z

I only know this via G. Ziegler's paper already cited, "Non-rational conﬁgurations, polytopes, and surfaces." I am not certain if Ulrich published it separately, as he was more concentrated on his universality theorem ("A universality theorem for realization spaces of maps").

Comment by Joseph O'Rourke

2013-05-05T01:09:31Z

However, note that there are nonrational, nonconvex polyhedral surfaces in $\mathbb{R}^3$, due to Ulrich Brehm.