4
votes
2answers
203 views

What is the smallest diameter ring a non-convex polyhedron can pass through in 3-space?

The question is mostly in the title. Imagine I have some non-convex polyhedron $P$, and I would like to find the smallest diameter ring that it can pass through in 3-space, undergoing any necessary ...
2
votes
2answers
465 views

Threading pinholes in the wall of cylinder to pass through an internal coordinate

Imagine I take a sheet of paper and use a pin to generate an $N$x$M$ rectangular array of small holes. I then fold the sheet to form a cylinder of radius $r_c$ and height $h_c$, where there are $N$ ...
1
vote
1answer
399 views

Decomposing a sphere (or defomed sphere) into a vertex-transitive graph with fixed-length curved edges

Please see the original problem specification (which Joseph O'Rourke was responding to in his answer) below. Motivation - I'm interested in a particular case of the problem where one wants to ...
1
vote
1answer
258 views

Constructing a graph that approximates a sphere using rotationally symmetric building blocks with equal numbers of edges

I'd like to construct a graph that approximates a sphere in 3-space, but I'm placed under the following constraints: (1) - I am only allowed to use a construction block, $v_i$, consisting of a single ...
1
vote
1answer
128 views

Inferring geometric properties of a polytope from intersection volumes of spheres at unknown coordinates on its surface

Let's say we have some polytope $P$ in 3-space (which is not necessarily convex) as well as some number of points on its surface, $(g_1, ..., g_N)$. We are provided no information about the ...
3
votes
5answers
572 views

Is the following two-dimensional graph likely to be globally rigid?

Consider the two-dimensional non-planar graph $G$, with known topology and edge lengths $(r_1, r_2, ... r_N) \in R$, but unknown vertex coordinates. We further specify that: All vertices within a ...
4
votes
2answers
312 views

Approximate search space on a 5x5x5 cube with 3 different possible classes?

Hey all, I read the meta, and I realize this question might be pretty elementary for this site, but I'm having trouble computing this, and I know it won't take too much insight for someone to give me ...
1
vote
0answers
373 views

Catmull-Clark Subdivision and weights

I've been toying with a Catmull-Clark subdivision algorithm; I also compared my results to results I found online (e.g. images.google.com). The weights used to relocate the old vertices of the mesh ...
2
votes
3answers
317 views

Can we uniquely define a graph to have the topology of a polytope via proper edge length selection?

I'll ask you to consider a situation wherein one has a series of edges for a graph, $(e_1, e_2, ..., e_N) \in E$, each with a specifiable length $(l_1, l_2, ..., l_N) \in L$, and the goal is to insure ...
4
votes
3answers
961 views

Optimal packing of spheres tangent to a central sphere

Please consider a central, ordinary 2-sphere $S_1$, of some radius $r_1$, and a second ordinary sphere, $S_2$, of radius $r_2$, where $r_2 \leq r_1$. My question concerns optimal values for the ...
8
votes
1answer
846 views

Expected number of steps for a discrete random walk to visit every point on an N-dimensional rectangular lattice

Please imagine a discrete random walk on an N-dimensional rectangular lattice with dimensional lengths $(l_1, ..., l_N) \in L$ and total lattice points $P = \prod{l_i}$, for $i = 1, ..., N$. At each ...
1
vote
4answers
1k views

Finding the union of N random circles arbitrarily (or conspiratorially) placed on a two-dimensional surface

Please consider a two-dimensional surface populated with a set of Cartesian coordinates $(x_i, y_i)$ for $N$ circles with individual radii $r_i$, where $r_{min} < r_i < r_{max}$. Here, the ...
1
vote
2answers
768 views

Calculating the surface area distribution of two-dimensional projections for a polytope

My question concerns the existence of a nice (deterministic?) method/algorithm for calculating the distribution of surface areas for two-dimensional projections of an arbitrary polytope (or convex ...
9
votes
4answers
657 views

Characterizing a tumbling convex polytope from the surface areas of its two-dimensional projections

My general question concerns what we can learn about an arbitrary, three-dimensional convex polytope (or convex hull of an arbitrary polytope) strictly from the surface areas of its two-dimensional ...
9
votes
2answers
451 views

When can a freely moving sphere escape from a 'cage' defined by a set of impassible coordinates?

To ask this question in a (hopefully) more direct way: Please imagine that I take a freely moving ball in 3-space and create a 'cage' around it by defining a set of impassible coordinates, $S_c$ ...
7
votes
2answers
556 views

Deciding membership in a convex hull

Problem: Given points $u,v_1,\dots,v_n\in\mathbb{R}^m$, decide if $u$ is contained in the convex hull of $v_1,\dots,v_n.$ This can be done efficiently by linear programming (time polynomial in ...