User joseph o'rourke - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T18:35:45Z http://mathoverflow.net/feeds/user/6094 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/131156/how-can-i-randomly-draw-an-ensemble-of-unit-vectors-that-sum-to-zero/131183#131183 Answer by Joseph O'Rourke for How can I randomly draw an ensemble of unit vectors that sum to zero? Joseph O'Rourke 2013-05-20T02:14:06Z 2013-05-20T03:06:15Z <p>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.</p> <p>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)$.</p> <p>Continue until there is sufficient "mixing." I illustrate the process below for 30 iterations applies to a hexagon. <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/HexVecs.gif" alt="HexVecsAnim" /> <br /> (Apologies for the scale&mdash;the chain wanders away from its initial locaion.)</p> http://mathoverflow.net/questions/130785/trilateration-problem/130822#130822 Answer by Joseph O'Rourke for Trilateration problem Joseph O'Rourke 2013-05-16T11:51:12Z 2013-05-16T11:51:12Z <p>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$: <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/ScaledTriangles.jpg" alt="ScaledTriangles" /> <br /> 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$.</p> http://mathoverflow.net/questions/130577/how-to-find-overlap-between-two-convex-hulls-along-with-the-overlap-area/130618#130618 Answer by Joseph O'Rourke for How to find overlap between two convex hulls,along with the overlap area Joseph O'Rourke 2013-05-14T18:26:17Z 2013-05-14T18:26:17Z <p>If you care about speed, then there is a linear-time algorithm specifically tuned to intersecting two convex polygons, described in the book, <a href="http://cs.smith.edu/~orourke/books/compgeom.html" rel="nofollow"><em>Computational Geometry in C</em></a>, with downloadable code. <hr /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/CGinCFig7.15.png" alt="Fig.7.15" /> <hr /> (I took the above snapshot from an illegal scan of the book!)</p> http://mathoverflow.net/questions/130396/applications-of-visual-calculus/130442#130442 Answer by Joseph O'Rourke for Applications of visual calculus Joseph O'Rourke 2013-05-12T22:15:09Z 2013-05-13T04:25:03Z <p>Perhaps this previous MO question may help: <a href="http://mathoverflow.net/questions/77175/taking-zooming-in-on-a-point-of-a-graph-seriously" rel="nofollow">Taking “Zooming in on a point of a graph” seriously</a>, e.g., this <a href="http://mathoverflow.net/questions/77175/taking-zooming-in-on-a-point-of-a-graph-seriously/77227#77227" rel="nofollow">answer link</a>.</p> http://mathoverflow.net/questions/130374/inferring-the-properties-of-a-visibility-blocker-tangential-to-a-point-like-light/130384#130384 Answer by Joseph O'Rourke for Inferring the properties of a visibility blocker tangential to a point-like light source Joseph O'Rourke 2013-05-12T00:23:07Z 2013-05-12T00:23:07Z <p>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): <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/SphericalDector.jpg" alt="SphericalDetector" /> <br /> In $\mathbb{R}^3$, you could not distinguish between a vertical and a horizontal segment $P$ (or a thickened segment $P$).</p> http://mathoverflow.net/questions/130255/optimal-inspection-path-on-a-sphere Optimal inspection path on a sphere Joseph O'Rourke 2013-05-10T12:14:15Z 2013-05-10T19:10:42Z <p>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.</p> <blockquote> <p><b>Q1</b>. For a given $d \in (0,\pi]$, what are the shortest such paths $\gamma(d)$?</p> </blockquote> <p>Two other ways to define $\gamma(d)$:</p> <ol> <li> The shortest path $\gamma$ such that every point on $S$ is no more than a distance $d$ from some point of $\gamma$. <li> The shortest path $\gamma$ such that the union of disks of radius $d$ centered on every point of $\gamma$ cover $S$. </ol> <p>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.: <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/SpiralOnSphere.jpg" alt="SpiralOnSphere" /> <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <sub>(Image from <a href="http://grabcad.com/library/spiral-wrapped-around-sphere" rel="nofollow">grabcad.com</a>.)</sub> <br /> 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$): <br /> &nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/SpherePaint12.jpg" alt="SpherePaint12" /> <br /> 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$.</p> <p>Perhaps this question can be answered even without precise understanding of $\gamma(d)$ for all $d$:</p> <blockquote> <p><b>Q2</b>. Does $\gamma(d)$ vary continuously with respect to $d$?</p> </blockquote> <p>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.</p> <blockquote> <p><b>Q3</b>. Has this question been studied before? It feels classical.</p> </blockquote> <p>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!</p> <p><hr /> (Related earlier MO questions: <a href="http://mathoverflow.net/questions/129726/optimal-paintbrush-geodesics" rel="nofollow">Optimal paintbrush geodesics</a>; <a href="http://mathoverflow.net/questions/69099/shortest-closed-curve-to-inspect-a-sphere" rel="nofollow">Shortest closed curve to inspect a sphere</a>.)</p> http://mathoverflow.net/questions/130228/straight-line-passing-through-a-convex-region/130269#130269 Answer by Joseph O'Rourke for Straight Line Passing Through a Convex Region Joseph O'Rourke 2013-05-10T15:01:04Z 2013-05-10T18:17:44Z <p>It so happens that Wikipedia contains an article entitled, "<a href="http://en.wikipedia.org/wiki/Intersection_of_a_polyhedron_with_a_line" rel="nofollow">Intersection of a polyhedron with a line</a>," but I doubt that answers your question.</p> <p>A better answer is provided by another MO question, "<a href="http://mathoverflow.net/questions/129570/" rel="nofollow">Intersection points of straight line segment with Voronoi diagram</a>": You can achieve $O(\log n)$ query time but only if you invest quadratic time preprocessing (which corroborates Ricky Demer's comment).</p> http://mathoverflow.net/questions/129759/modern-mathematical-achievements-accessible-to-undergraduates/129767#129767 Answer by Joseph O'Rourke for Modern Mathematical Achievements Accessible to Undergraduates Joseph O'Rourke 2013-05-05T20:00:30Z 2013-05-07T01:41:05Z <p>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 <a href="http://en.wikipedia.org/wiki/Kepler_conjecture#Hales.27_proof" rel="nofollow">proof outline and technique</a> are accessible, but it would be a stretch to say that the proof is "accessible to undergraduates" (or to anyone, for that matter!).</p> <p>I have had some success explaining to undergraduates the proof of the <a href="http://en.wikipedia.org/wiki/Bellows_conjecture" rel="nofollow">Bellows Conjecture</a>: 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 <a href="http://www.mathpages.com/home/kmath424/kmath424.htm" rel="nofollow">Francesca's 15th-century formula</a> 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. <br /> <img src="http://cs.smith.edu/~orourke/MathOverflow/Steffen-folded.jpg" alt="Steffen" /><br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<sub>Steffen's 14-triangle, 9-vertex flexible polyhedron (Fig.23.9 in <a href="http://gfalop.org/" rel="nofollow">Geometric Folding Algorithms</a>).</sub></p> http://mathoverflow.net/questions/129726/optimal-paintbrush-geodesics Optimal paintbrush geodesics Joseph O'Rourke 2013-05-05T15:04:48Z 2013-05-05T15:04:48Z <p>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$: <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/TorusGeodesicPaint.jpg" alt="TorusGeodesicPaint" /><br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <sub>(Image based on one at <a href="http://www.rdrop.com/~half/math/torus/illustrating.html" rel="nofollow">rdrop.com</a>.)</sub> <br /></p> <blockquote> <p><b>Q1</b>. For a given $S$, which $\gamma(w)$ have the properties that (a)&nbsp;all of $S$ is covered by $\gamma(w)$, and (b)&nbsp;the <em>area product</em> $\;|\gamma| \cdot w$ is minimized, where $|\gamma|$ is the length of $\gamma$.</p> </blockquote> <p>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$.</p> <blockquote> <p><b>Q2</b>. Is the semi-great circle indeed optimal for the sphere?</p> <p><b>Q3</b>. Are there other clear examples of optimal paintbrush geodesics?</p> <p><b>Q4</b>. Has this notion been studied before, perhaps in another guise?</p> </blockquote> <p>Thanks for ideas/pointers!</p> http://mathoverflow.net/questions/129570/intersection-points-of-straight-line-segment-with-voronoi-diagram/129572#129572 Answer by Joseph O'Rourke for Intersection points of straight line segment with Voronoi diagram Joseph O'Rourke 2013-05-03T19:26:30Z 2013-05-03T20:50:02Z <p>The paper by Chazelle and Liu,</p> <blockquote> <p>"Lower bounds for intersection searching and fractional cascading in higher dimension." 2001. (<a href="http://dl.acm.org/citation.cfm?id=380818" rel="nofollow">ACM link</a>)</p> </blockquote> <p>shows that for planar convex subdivisions, the answer is <em>Yes</em>, there is a computationally efficient method <strong>if</strong> you allow quadratic storage, but <em>No</em> if you insist on subquadratic storage: <hr /> &nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/ChazelleQuery.png" alt="Chazelle" /> <hr /> Your one hope is that, because a Voronoi diagram is a special convex subdivision, this result can be improved by exploiting its Voronoi-ness.</p> http://mathoverflow.net/questions/128940/random-rings-linked-into-one-component Random rings linked into one component? Joseph O'Rourke 2013-04-27T17:56:13Z 2013-05-01T12:18:23Z <p>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).</p> <blockquote> <p><b>Q1</b>. As $n \to \infty$, does the probability that all the rings in $C_n$ are linked together in one component approach $1$?</p> </blockquote> <p>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: <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/RandCircleLinks.jpg" alt="RandCircleLinks" /> <br /></p> <blockquote> <p><b>Q2</b>. Same as <b>Q1</b>, but with $S$ a sphere of some (perhaps large) radius $r > 1$.</p> <p><b>Q3</b>. Same as <b>Q1</b>, except with $S$ an arbitrary convex body, e.g., a cube.</p> </blockquote> <p>I feel the answer to <b>Q1</b> should be <em>Yes</em>, but I am less certain of <b>Q3</b>. 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!</p> <p><b>Answered</b> (<em>1May13</em>). 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 <em>Yes</em>, even without the assumption that $S$ is convex. Thanks for the interest!</p> http://mathoverflow.net/questions/129204/intersection-of-2-visibility-polygons/129210#129210 Answer by Joseph O'Rourke for Intersection of 2 visibility polygons Joseph O'Rourke 2013-04-30T11:58:13Z 2013-05-01T11:36:01Z <p>Here is an argument, a revision (and replacement) of one I sketched earlier.</p> <p>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.</p> <p>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: <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/VisibSeg.jpg" alt="VisibSeg" /> <br /></p> http://mathoverflow.net/questions/128146/can-every-mathbbz2-disk-be-pinball-reached Can every $\mathbb{Z}^2$ disk be pinball-reached? Joseph O'Rourke 2013-04-20T01:03:31Z 2013-04-28T14:06:39Z <p>Let every point of $\mathbb{Z}^2$ be surrounded by a mirrored disk of radius $r &lt; \frac{1}{2}$, except leave the origin $(0,0)$ unoccupied by a disk.</p> <blockquote> <p><b>Q</b>. Is it the case that every disk can be hit by a lightray emanating from the origin and reflecting off the mirrored disks?</p> </blockquote> <p>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: <br /> <img src="http://cs.smith.edu/~orourke/MathOverflow/PinballAll.jpg" alt="PinballAll" /> <br /></p> <p>I believe the answer to my question <b>Q</b> is <em>Yes</em>, 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, "<a href="http://mathoverflow.net/questions/89293/" rel="nofollow">Pinball on the infinite plane</a>.")</p> <p>It occurs to me it might be interesting to color the disks according to the minimum number of reflections needed to hit each...</p> http://mathoverflow.net/questions/128146/can-every-mathbbz2-disk-be-pinball-reached/128969#128969 Answer by Joseph O'Rourke for Can every $\mathbb{Z}^2$ disk be pinball-reached? Joseph O'Rourke 2013-04-28T00:20:46Z 2013-04-28T00:20:46Z <p>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}$: <br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="http://cs.smith.edu/~orourke/MathOverflow/RadiusHalf.jpg" alt="alt text"><br /></p> http://mathoverflow.net/questions/128869/incidences-of-quadratic-forms-and-points/128875#128875 Answer by Joseph O'Rourke for Incidences of quadratic forms and points Joseph O'Rourke 2013-04-27T00:05:18Z 2013-04-27T00:05:18Z <p>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,</p> <blockquote> <p>"Incidences between points and non-coplanar circles." <a href="http://arxiv.org/abs/1208.0053" rel="nofollow">arXiv:1208.0053 (math.CO)</a></p> </blockquote> <p>showed that the number of incidences between $m$ points and $n$ arbitrary circles in three dimensions&mdash;in the situation when the circles are "truly three-dimensional," in the sense that there exists a $q &lt; n$ so that no sphere or plane contains more than $q$ of the circles&mdash;then the number of incidences is </p> <p>$$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).$$</p> <p>The complexity of this result illustrates the complexity of the topic!</p> <p><br />&nbsp;&nbsp;&nbsp;<img src="http://cs.smith.edu/~orourke/MathOverflow/BorisCirclePts.png" alt="alt text"> <br /><sub>(Figure from Boris Aronov, Vladlen Koltun, Micha Sharir, "Incidences between Points and Circles in Three and Higher Dimensions," <em>Discrete &amp; Computational Geometry</em>. February 2005, Volume 33, Issue 2, pp 185-206. (<a href="http://link.springer.com/article/10.1007/s00454-004-1111-9" rel="nofollow">Springer link</a>).) </sub></p> http://mathoverflow.net/questions/128814/weighted-graph-plot/128836#128836 Answer by Joseph O'Rourke for weighted graph plot Joseph O'Rourke 2013-04-26T16:20:53Z 2013-04-26T19:54:18Z <p>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 <a href="https://gephi.org/" rel="nofollow">Gephi</a>, which permits one to alter the layout parameters interactively: </p> <p><br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="https://gephi.org/wp-content/uploads/2011/06/forceatlas2.jpg" alt="alt text"><br /> <br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<sub>(Image from <a href="https://gephi.org/2011/forceatlas2-the-new-version-of-our-home-brew-layout/" rel="nofollow">this link</a>.)</sub></p> http://mathoverflow.net/questions/128519/secondary-polytope-simplicial/128559#128559 Answer by Joseph O'Rourke for Secondary Polytope Simplicial? Joseph O'Rourke 2013-04-24T00:12:00Z 2013-04-24T12:01:02Z <p>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" (<em><a href="http://cs.smith.edu/~orourke/books/discrete.html" rel="nofollow">Handbook of Discrete and Computational Geometry</a></em>), and the second from Sven Herrmann's paper, "On the facets of the secondary polytope" (<a href="http://arxiv.org/abs/0908.2537" rel="nofollow">arXiv.0908.2737v3</a>). 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$. <hr /> &nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/SecondaryPolytope.jpg" alt="SecondaryPolytope" /> <hr /> Each vertex of the secondary polytope corresponds to a triangulation of the point set.</p> <p>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 <a href="http://en.wikipedia.org/wiki/Simplicial_polytope" rel="nofollow">simplicial polytope</a> 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. <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/PentagonAssoc.png" alt="PentagonAssoc" /> <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <sub>(Image from <a href="http://cs.smith.edu/~orourke/DCG/" rel="nofollow"><em>Discrete and Computational Geometry</em></a>)</sub></p> http://mathoverflow.net/questions/128197/trapping-of-discs-after-random-sequential-adsorption/128200#128200 Answer by Joseph O'Rourke for "Trapping" of discs after random sequential adsorption Joseph O'Rourke 2013-04-21T00:31:14Z 2013-04-21T00:31:14Z <p>This is not an knowledgeable answer, so forgive me if this is irrelevant.</p> <p>The paper, "Random sequential adsorption," by Jens Feder (<a href="http://www.sciencedirect.com/science/article/pii/0022519380903586" rel="nofollow">Elsevier link</a>), 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...? </p> <blockquote> <p><b>Abstract</b>. 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. [...]</p> </blockquote> <p><br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/JammedDisks.png" alt="JammedDisks" /> <br /></p> http://mathoverflow.net/questions/127530/surfaces-filled-densely-by-a-geodesic Surfaces filled densely by a geodesic Joseph O'Rourke 2013-04-14T13:02:43Z 2013-04-20T14:11:23Z <blockquote> <p>Which smooth, closed surfaces $S \subset \mathbb{R}^3$ have no single geodesic $\gamma$ that fills $S$ densely?</p> </blockquote> <p>Say a geodesic $\gamma$ "fills $S$ densely" if the closure of the set of points through which $\gamma$ passes equals $S$. Some examples:</p> <ul> <li> A sphere: every geodesic is a great circle. <li> Zoll surfaces, as discussed here: "<a href="http://mathoverflow.net/questions/28622/28627#28627" rel="nofollow">Surfaces all of whose geodesics are both closed and simple</a>." <li> An ellipsoid. <br /> <img src="http://geographiclib.sourceforge.net/1.29/triaxial-equatorial-a.png" /><br /> (Image from <a href="http://geographiclib.sourceforge.net/1.29/triaxial.html" rel="nofollow">GeographicLib</a>.) <br /> <li> <br /> A torus generally has many geodesics that fill the surface. <br /> <img src="http://cs.smith.edu/~orourke/MathOverflow/torgeo2.jpg" /> <br /> (<a href="http://academic.csuohio.edu/oprea_j/dgbook/dgbook4.html" rel="nofollow">Image by John Oprea</a>) <br /> </ul> <p>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! <hr /> <b>Answers Summary</b> (<em>18Apr2013</em>):</p> <ul> <li> (Robert Bryant, Mikhail Katz) Any surface of revolution with poles has no dense geodesic. This holds for convex or nonconvex surfaces of revolution. <li> (Robert Bryant) There are generalizations of Liouville surfaces (due to Goryachev-Chaplygin and to Dullin-Matveev) that have no dense geodesic. <li> (Misha Kapovich) Every surface may be perturbed by gluing on "focusing caps" so that it has dense geodesics. <li> (Keith Burns) Guess: There is always a dense geodesic on a closed Riemannian surface of genus $\ge 2$. </ul> http://mathoverflow.net/questions/128088/lecture-on-fractals-for-middle-school-students/128107#128107 Answer by Joseph O'Rourke for Lecture on Fractals for Middle School Students Joseph O'Rourke 2013-04-19T16:24:45Z 2013-04-19T23:31:16Z <p>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 <code>znew = zold² + c</code>, 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: <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="http://lodev.org/cgtutor/images/juliaset.gif" alt="Julia set"><br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<sub>(Image from <a href="http://lodev.org/cgtutor/juliamandelbrot.html" rel="nofollow">cgtutor</a>)</sub><br /></p> <p>With this understanding secured, you might be able to introduce complex numbers.</p> <p>For motivating applications, you could easily connect to the use of fractals in computer graphics in movies (<em>Lord of the Rings</em>; <em>The Hobbit</em>, etc.): <br /> &nbsp;&nbsp;<img src="http://2.bp.blogspot.com/_iLtwy6ZDGfw/TBdlz7GVzoI/AAAAAAAAABs/3aUogqFtYpI/s1600/cool2.jpg" alt="FractalMountain"><br /> &nbsp;&nbsp;<sub>(Image from <a href="http://lifeinwireframe.blogspot.com/2010/06/f-irst-of-all-fractals-are-bloody-huge.html" rel="nofollow">LifeInWireframe</a>)</sub><br /></p> http://mathoverflow.net/questions/127734/nash-embedding-theorems-for-pseudo-riemannian-manifolds/127774#127774 Answer by Joseph O'Rourke for Nash Embedding Theorems for Pseudo-Riemannian Manifolds? Joseph O'Rourke 2013-04-16T23:53:36Z 2013-04-17T00:05:11Z <p>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:</p> <p>"The embedding of General Relativity in five dimensions." Carlos Romero, Reza Tavakol, Roustam Zalaletdinov. <em>General Relativity and Gravitation</em>. March 1996, Volume 28, Issue 3, pp 365-376. (<a href="http://link.springer.com/article/10.1007/BF02106973" rel="nofollow">Springer link</a>.)</p> <blockquote> <p><b>Abstract</b>. 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. [...]</p> </blockquote> <p>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, <em>J. Math. Phys.</em> 43, 3097 (2002). (<a href="http://jmp.aip.org/resource/1/jmapaq/v43/i6/p3097_s1?isAuthorized=no" rel="nofollow">AIP link</a>.)</p> http://mathoverflow.net/questions/127423/how-many-vertices-can-a-convex-polytope-have/127429#127429 Answer by Joseph O'Rourke for How many vertices can a convex polytope have? Joseph O'Rourke 2013-04-13T00:07:15Z 2013-04-13T00:07:15Z <p>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 <em>Upper Bound Theorem</em>, realized by duals of <a href="http://en.wikipedia.org/wiki/Cyclic_polytope" rel="nofollow">cyclic polytopes</a>. 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. <br /> &nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/CyclicPolytope.png" alt="CyclicPolytope" /> <br /> See, e.g.,</p> <blockquote> <p>"Basic Properties Of Convex Polytopes." Martin Henk, Jürgen Richter-Gebert, and Günter M. Ziegler. <em><a href="http://cs.smith.edu/~orourke/books/discrete.html" rel="nofollow">Handbook of Discrete and Computational Geometry</a></em>, Chapter 16. CRC Press. 2004. (<a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.7517" rel="nofollow">CiteSeer link</a>)</p> </blockquote> http://mathoverflow.net/questions/127283/convex-representation-of-planar-graphs/127299#127299 Answer by Joseph O'Rourke for Convex representation of (planar) graphs Joseph O'Rourke 2013-04-12T00:03:48Z 2013-04-12T00:03:48Z <p>Although what constitutes a "practical justification" is in the eye of the beholder, I would think this might qualify.</p> <p>There is a notion called <em>geometric routing</em> 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 <em>greedy routing</em>, 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.</p> <p>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:</p> <blockquote> <p>He, Zhang. "A simple routing algorithm based on Schnyder coordinates." <em>Theoretical Computer Science</em>. February 2013. (<a href="http://www.sciencedirect.com/science/article/pii/S0304397513000674" rel="nofollow">Elsevier link</a>)</p> </blockquote> <p><br /> &nbsp;<img src="http://cs.smith.edu/~orourke/MathOverflow/HeZhang.png" alt="alt text"></p> http://mathoverflow.net/questions/127229/separation-of-anti-hole-inequality/127236#127236 Answer by Joseph O'Rourke for Separation of Anti-Hole Inequality Joseph O'Rourke 2013-04-11T12:41:57Z 2013-04-11T12:41:57Z <p>Here is one reference, a 2010 book that may lead to other literature: <em>Polyhedral and Semidefinite Programming Methods in Combinatorial Optimization</em>, by Levent Tunçel:</p> <p><br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/AntiHoles.png" alt="AntiHoles" /> <br /></p> http://mathoverflow.net/questions/126991/constrained-triangulation-of-a-convex-polytope/126996#126996 Answer by Joseph O'Rourke for Constrained Triangulation of a Convex Polytope Joseph O'Rourke 2013-04-09T16:36:40Z 2013-04-09T23:53:11Z <p>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 <a href="http://en.wikipedia.org/wiki/Sch%C3%B6nhardt_polyhedron" rel="nofollow">Schönhardt polyhedron</a>, 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.</p> <p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="http://upload.wikimedia.org/wikipedia/commons/thumb/f/f3/Sch%C3%B6nhardt_polyhedron.svg/220px-Sch%C3%B6nhardt_polyhedron.svg.png" alt="alt text"><br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<sub>(<a href="http://en.wikipedia.org/wiki/Sch%C3%B6nhardt_polyhedron" rel="nofollow">Image from Wikipedia</a>)</sub></p> <p>If you want to nevertheless hope that your region can be triangulated, you might explore <a href="http://www.voronoi.com/wiki/index.php?title=Bistellar_flips" rel="nofollow">geometric bistellar flips</a> to underlie an approach.</p> http://mathoverflow.net/questions/125224/rational-points-on-a-sphere-in-mathbbrd Rational points on a sphere in $\mathbb{R}^d$ Joseph O'Rourke 2013-03-22T01:34:24Z 2013-04-09T19:56:37Z <p>Call a point of $\mathbb{R}^d$ <em>rational</em> if all its $d$ coordinates are rational numbers.</p> <blockquote> <p><b>Q1</b>. 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?</p> </blockquote> <p>This is certainly true for $d=2$, <a href="http://en.wikipedia.org/wiki/Group_of_rational_points_on_the_unit_circle" rel="nofollow">rational points on the unit circle</a>.</p> <blockquote> <p><b>Q2</b>. If (as I suspect) the answer to Q1 is <em>Yes</em>, is there a sense in which the rational coordinates are becoming arithmetically more complicated with larger $d$, say in terms of their <em>height</em>?</p> </blockquote> <p>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$.</p> <p>This is far from my expertise. No doubt this is known, in which case a pointer would suffice. Thanks! <hr /> (Added, <em>22Mar13</em>). I just found this reference. [Earlier misleading remark removed.]</p> <blockquote> <p>Klee, Victor, and Stan Wagon. <em>Old and new unsolved problems in plane geometry and number theory</em>. No. 11. Mathematical Association of America, 1996. p.135.</p> </blockquote> <p><br /> &nbsp;<img src="http://cs.smith.edu/~orourke/MathOverflow/KleeWagon10.8.png" alt="KleeWagonFig10.8"></p> http://mathoverflow.net/questions/126575/combinatorial-distance-between-simplicial-complexes Combinatorial distance between simplicial complexes Joseph O'Rourke 2013-04-04T23:50:46Z 2013-04-06T01:59:24Z <p>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.</p> <p>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 <em>renovation distance</em> between $K_1$ and $K_2$.</p> <p>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) (<em>Example corrected 5Apr13</em> by Vidit Nanda comment): <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/SimplicialComplex.jpg" alt="SimplicialComplex" /> <br /> 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. (<em>Update 5Apr13</em>: Vidit Nanda observes that a special case is <a href="http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem" rel="nofollow">subgraph isomorphism</a>, an NP-complete problem.)</p> <p>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!</p> http://mathoverflow.net/questions/28758/uppercase-point-labels-in-high-school-diagrams-from-euclid Uppercase Point Labels in High-School Diagrams: from Euclid? Joseph O'Rourke 2010-06-19T16:15:46Z 2013-04-06T00:46:44Z <p>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 <em>La Geometrie</em> (1637) follow the same convention.</p> <p>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.</p> <p>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?</p> http://mathoverflow.net/questions/65677/is-there-a-midsphere-theorem-for-4-polytopes Is there a midsphere theorem for 4-polytopes? Joseph O'Rourke 2011-05-21T20:44:44Z 2013-04-02T14:08:42Z <p>The (remarkable) <a href="http://en.wikipedia.org/wiki/Midsphere" rel="nofollow"><em>midsphere</em> theorem</a> 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). <br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="http://cs.smith.edu/~orourke/MathOverflow/MidSpheres.jpg" alt="MidSpheres"><br /></p> <blockquote> <p><b>Q1.</b> Is there an analogous theorem for 4-polytopes, that each combinatorial type may be realized by a polytope with <a href="http://mathworld.wolfram.com/Ridge.html" rel="nofollow">ridges</a> (or edges?) tangent to a 3-sphere?</p> </blockquote> <p>Because the proofs of the midsphere theorem rely on the Koebe–Andreev–Thurston <a href="http://en.wikipedia.org/wiki/Circle_packing_theorem" rel="nofollow">circle-packing theorem</a>, a related query is:</p> <blockquote> <p><b>Q2.</b> Is there a generalization of the circle-packing theorem to sphere-packing?</p> </blockquote> <p>Both questions may be generalized to arbitrary dimension.</p> <p>I suspect the answer to both questions may be <em>No</em>, in which case a pointer would suffice. Thanks!</p> http://mathoverflow.net/questions/126066/symmetric-dominance-regions-surrounding-a-gaussian-prime Symmetric dominance regions surrounding a Gaussian prime Joseph O'Rourke 2013-03-31T02:48:02Z 2013-03-31T02:48:02Z <p>Let $z=a + b i$ be a complex number which is a <a href="http://mathworld.wolfram.com/GaussianPrime.html" rel="nofollow">Gaussian prime</a>, 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 <a href="http://en.wikipedia.org/wiki/Orthogonal_convex_hull" rel="nofollow">orthogonally convex polygon</a> surrounding $z$ that is empty of Gaussian primes. ($D$ for <em>Dominance</em>.) 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: <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/GPDom2.jpg" alt="GPDom2" /> <br /> It seems likely that $D(z)$ is not well-defined, based on a comment of François Brunault to an earlier MO question, "<a href="http://mathoverflow.net/questions/91423/gaussian-prime-spirals" rel="nofollow">Gaussian prime spirals</a>":</p> <blockquote> <p>it's unknown whether there are infinitely many Gaussian primes of the form $n+i$ with $n \in \mathbb{Z}$.</p> </blockquote> <p>Nevertheless, I wonder if this question might avoid running into an unsolved problem:</p> <blockquote> <p><b>Q</b>. 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$?</p> </blockquote> <p>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.</p> <p>My guess is that the answer to <b>Q</b> is <em>Yes</em>, 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!</p> http://mathoverflow.net/questions/131156/how-can-i-randomly-draw-an-ensemble-of-unit-vectors-that-sum-to-zero Comment by Joseph O'Rourke Joseph O'Rourke 2013-05-21T17:47:02Z 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, <i>Topolo. Appl.</i> 112(2) (2001) 137–174. http://mathoverflow.net/questions/131156/how-can-i-randomly-draw-an-ensemble-of-unit-vectors-that-sum-to-zero/131183#131183 Comment by Joseph O'Rourke Joseph O'Rourke 2013-05-20T02:27:44Z 2013-05-20T02:27:44Z @Alekk: Sorry, I cannot even guess. Perhaps others can... http://mathoverflow.net/questions/130878/regularity-of-delaunay-triangulation-of-a-hypercube Comment by Joseph O'Rourke Joseph O'Rourke 2013-05-16T23:42:35Z 2013-05-16T23:42:35Z Perhaps you are already familiar with the notion of a <i>fat triangulation</i>, 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 &quot;regular triangulations&quot; are yet a different concept.) http://mathoverflow.net/questions/130577/how-to-find-overlap-between-two-convex-hulls-along-with-the-overlap-area/130618#130618 Comment by Joseph O'Rourke Joseph O'Rourke 2013-05-14T18:46:40Z 2013-05-14T18:46:40Z @meij: Yes! But of course that is the usual result of the convex hull computation. http://mathoverflow.net/questions/130492/higher-dimensional-convex-hull/130501#130501 Comment by Joseph O'Rourke Joseph O'Rourke 2013-05-13T16:25:46Z 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 <i>Yes</i>. http://mathoverflow.net/questions/130374/inferring-the-properties-of-a-visibility-blocker-tangential-to-a-point-like-light/130384#130384 Comment by Joseph O'Rourke Joseph O'Rourke 2013-05-12T13:16:33Z 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. http://mathoverflow.net/questions/130363/non-convex-polytope-definition Comment by Joseph O'Rourke Joseph O'Rourke 2013-05-12T00:54:48Z 2013-05-12T00:54:48Z The title of your question (&quot;non-convex&quot;) does not match the question itself. Perhaps you are seeking a definition of a <i>polytopal complex</i>? This is defined in Ziegler's <i>Lectures on Polytopes</i>. http://mathoverflow.net/questions/130374/inferring-the-properties-of-a-visibility-blocker-tangential-to-a-point-like-light Comment by Joseph O'Rourke Joseph O'Rourke 2013-05-11T23:38:42Z 2013-05-11T23:38:42Z Is this a correct interpretation? The &quot;detector&quot; 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. http://mathoverflow.net/questions/130255/optimal-inspection-path-on-a-sphere Comment by Joseph O'Rourke Joseph O'Rourke 2013-05-10T16:38:30Z 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... http://mathoverflow.net/questions/129948/partition-graph Comment by Joseph O'Rourke Joseph O'Rourke 2013-05-07T11:51:42Z 2013-05-07T11:51:42Z &quot;It is straightforward to compute the connected components of a graph in linear time&quot;: <a href="http://en.wikipedia.org/wiki/Connected_component_(graph_theory)#Algorithms" rel="nofollow">en.wikipedia.org/wiki/&hellip;</a> http://mathoverflow.net/questions/129759/modern-mathematical-achievements-accessible-to-undergraduates/129767#129767 Comment by Joseph O'Rourke Joseph O'Rourke 2013-05-07T01:41:34Z 2013-05-07T01:41:34Z Thank you for the correction! http://mathoverflow.net/questions/129726/optimal-paintbrush-geodesics Comment by Joseph O'Rourke Joseph O'Rourke 2013-05-05T16:50:50Z 2013-05-05T16:50:50Z @Will: Yes, I think so! Which is why this concept has not been studied---It's essentially empty. :-) http://mathoverflow.net/questions/129726/optimal-paintbrush-geodesics Comment by Joseph O'Rourke Joseph O'Rourke 2013-05-05T16:36:48Z 2013-05-05T16:36:48Z @Sergei: Ah, very nice! http://mathoverflow.net/questions/129677/does-every-convex-polyhedron-have-a-combinatorially-isomorphic-counterpart-whose/129685#129685 Comment by Joseph O'Rourke Joseph O'Rourke 2013-05-05T02:15:11Z 2013-05-05T02:15:11Z I only know this via G. Ziegler's paper already cited, &quot;Non-rational conﬁgurations, polytopes, and surfaces.&quot; I am not certain if Ulrich published it separately, as he was more concentrated on his universality theorem (&quot;A universality theorem for realization spaces of maps&quot;). http://mathoverflow.net/questions/129677/does-every-convex-polyhedron-have-a-combinatorially-isomorphic-counterpart-whose/129685#129685 Comment by Joseph O'Rourke Joseph O'Rourke 2013-05-05T01:09:31Z 2013-05-05T01:09:31Z However, note that there are nonrational, <i>nonconvex</i> polyhedral surfaces in $\mathbb{R}^3$, due to Ulrich Brehm.