Finite or discrete collections of geometric objects. Packings, tilings, polyhedra, polytopes, intersection, arrangements, rigidity.

learn more… | top users | synonyms (1)

2
votes
1answer
193 views

Min Bend Orthogonal Knots

I am seeking literature on 3D orthogonal drawings of knots, especially minimum bend drawings. An orthogonal drawing employs segments parallel to the axes of a Cartesian coordinate system. A bend is a ...
1
vote
1answer
109 views

Generalizing the internal angle of a graph in $\mathbb{E}^2$ to $\mathbb{S}^2$

I am currently working on research involving packing problems and am finding myself needing the tools from Combinatorial Geometry (in particular, I've been reading Pach and Agarwal's book on the ...
4
votes
1answer
289 views

Planar sets closed under intersection of circles

Let $P$ be the plane with a point at infinity. By plane, I mean the Euclidian plane, and therefore it has circles. A line is also a circle, though its center is at infinity. If $A\subset P$ has ...
10
votes
2answers
286 views

Acute triangulation

Assume that $S$ is a finite 2-dimensional simplicial complex equipped with a metric $d$ such that each triangle is isometric to a plane triangle (so $(S,d)$ is a polyhedral space). Is it possible ...
45
votes
2answers
2k views

vector balancing problem

I believe the solution posted to the arXiv on June 17 by Marcus, Spielman, and Srivastava is correct. This problem may be hard, so I don't expect an off-the-cuff solution. But can anyone suggest ...
3
votes
1answer
316 views

from affine matroid to measures

Let $S$ be an arbitrary finite spanning subset of $\mathbb{R}^d$ of cardinality $N$. Let $W(S)$ be the formal $\mathbb{R}$-vector space generated by all $d$-dimensional simplices (i.e. bases of the ...
2
votes
1answer
163 views

Lipshitz Constant of the convex extension of a submodular function

The title says it all :) Given a submodular function (take the rank function of a matroid, for a concrete example) $f:\{0,1\}^n\rightarrow \mathbb{R}$, we can extend it to a convex function ...
2
votes
2answers
556 views

maximum number of shortest path among a set of n triangle obstacles

Assume that we have a two distinct points. The number of shortest path between these two points is one. When we add a triangle obstacle to the plane and this triangle intersects the line connecting ...
6
votes
1answer
312 views

Polygons that are hard to guard

Given an $n$-vertex polygonal 'art gallery' $P$ in the plane, it is possible to cover the interior of $P$ by placing 'guards' at (at worst) $\lfloor n/3\rfloor$ of the vertices of $P$. That this is ...
3
votes
1answer
332 views

Transience of self avoiding random walks on $\mathbb{Z}^d$

I'm finishing up a masters thesis in computer science and want to say a bit in the introduction about self-avoiding walks. My thesis looks at a random process which arose in computer science and my ...
0
votes
1answer
341 views

On the number of lines of given points

Hi all, I have a question Concerning Beck's theorem. I have read it from http://en.wikipedia.org/wiki/Beck%27s_theorem and I have two questions : I suppose Beck's theorem doesn't hold when instead ...
8
votes
1answer
452 views

Triangulations of polytopes and tilings of zonotopes

Consider a set $A = \{ a_1,a_2,\ldots, a_n \} $ of vectors in $\mathbb{R}^d$, which lie in a common affine hyperplane. Two convex polytopes may be obtained from $A$, namely the convex hull of the ...
9
votes
2answers
303 views

The area of the intersection of convex sets with prescribed pairwise intersections

Consider two numbers $a>b>0$. Let $A_1,A_2,A_3$ be three convex sets in ${\mathbb R}^2$ such that $\mu(A_i)=a$, $\mu(A_i\cap A_j)=b$ ($\mu$ is the usual measure on ${\mathbb R}^2$). What is the ...
11
votes
1answer
190 views

Metric conditions on configurations of points with only finitely many solutions

There is an old puzzle, which I believe I learned from Nob Yoshigahara, that asks for all configurations of four (distinct) points in the plane such that the six pairwise distances assume only two ...
8
votes
3answers
623 views

Small 4-chromatic coin graphs

A coin graph is a graph that can be represented by a set of disjoint, except possibly touching, unit disks in the plane (i.e. the disks are the vertices and the edges correspond to the pairs that ...
10
votes
0answers
275 views

Update to Shephard's “Twenty Problems on Convex Polyhedra”

Forty-three years ago, Geoffrey Shephard published an influential list of open problems on convex polyhedra. Progress has been made on several of his problems, and perhaps some have been completely ...
7
votes
1answer
840 views

Primes that are the sum of three squares

This is in some sense an extension of the earlier MO question, "Gaussian prime spirals." Gaussian primes in the complex plane, $a+b i$, require $a^2 +b^2$ prime off the axes. The generalization to ...
15
votes
3answers
1k views

Is Euler characteristic of a simplicial complex upper bounded by a polynomial in the number of its facets ?

What is the best upper bound known on the (absolute value of) the Euler characteristic of a simplicial complex in terms of the number of its facets ? In particular, I am interested in proving or ...
84
votes
5answers
5k views

Gaussian prime spirals

Imagine a particle in the complex plane, starting at $c_0$, a Gaussian integer, moving initially $\pm$ in the horizontal or vertical directions. When it hits a Gaussian prime, it turns left ...
3
votes
2answers
193 views

Form a $\mathbb{Z}^d$ lattice cycle from given lengths

Suppose you are given a list of integer lengths, e.g., $(5,3,2,2,1,1,2,1,1)$. The task is to decide if they can form a closed cycle in $\mathbb{Z}^d$ by connecting segments of those lengths in order, ...
4
votes
2answers
497 views

On the joints problem in finite fields

The original version of the so-called "joints problem" consists of the following: Let $L$ be a set of lines in $\mathbb{R}^{3}$. Determine the maximum number of "joints" determined by these lines, ...
26
votes
2answers
618 views

Careless packing

The sequence $\frac{1}{2}, \frac{1}{2\cdot 2}, \frac{1}{3\cdot 4}, \frac{1}{4\cdot 6}, \frac{1}{5\cdot 8}, \frac{1}{6\cdot 10},\ldots$ has a curious property, as follows: a) the series with these ...
17
votes
2answers
1k views

Erdős-Szekeres for first differences

The classical Erdős-Szekeres theorem says that any sequence of $n^2+1$ real numbers contains a monotonic $(n+1)$-term subsequence. Suppose, however, that we want to find a subsequence which is not ...
17
votes
3answers
692 views

Sperner Lemma Applications

I was always fascinated with this result. Sperner's lemma is a combinatorial result which can prove some pretty strong facts, as Brouwer fixed point theorem. I know at least another application of ...
6
votes
0answers
798 views

Interpolating points with minimum curvature constraint

I have $n$ points $p_i$ strictly interior to a rectangle $R$, and I would like to connect them with a curve $C$ whose curvature is as low as possible. Let $\kappa_\max(C)$ be the sharpest (largest ...
4
votes
2answers
378 views

Conformal structure does not see conical singularities

the conformal structure does not see the conical singularities of a polyhedral surface. This is a quote from the Preface of Quantum Triangulations (eds.: Carfora, Marzuoli). The sentiment is ...
3
votes
3answers
271 views

Vertex-transitive polytopes in any dimension with any number of vertices?

Given positive integers $d$ and $v$ with $v \geq d+1$, does there always exist a (convex) vertex-transitive $d$-polytope with $v$ vertices? It seems that the answer should be "obviously" true, but I ...
3
votes
1answer
436 views

Tverberg partitions with less than (r-1)(d+1)+1 points

The Tverberg Theorem states the following: Let $x_1,x_2,\dots, x_m$ be points in $R^d$ with $m \ge (r-1)(d+1)+1$. Then there is a partition $S_1,S_2,\dots, S_r$ of $\{1,2,\dots,m\}$ such that $\cap ...
2
votes
0answers
239 views

Erdős-Szekeres empty pseudoconvex $k$-gons

I am wondering if the Erdős-Szekeres empty convex $k$-gon question has a different answer if convexity is replaced by a pseudoline-version of convexity. The empty convex $k$-gon question is a variant ...
10
votes
1answer
512 views

Polygons uniquely inducing arrangements

A beautiful, relatively recent result is that, Every simple arrangement $\cal{A}$ of $n$ lines in the plane is induced by a simple $n$-gon $P$. In a simple arrangement, every pair of lines ...
7
votes
1answer
266 views

Does the Hirsch conjecture hold for $n < 2d$?

The Hirsch conjecture asserts that the graph (i.e. $1$-skeleton) of a $d$-dimensional convex polytope with $n$ facets has diameter at most $n - d$. After being open for decades, Francisco Santos has ...
7
votes
3answers
252 views

Expected minimum face angle of random convex polyhedron in $\mathbb{R}^3$

Let $P_n$ be a "random convex polyhedron" in $\mathbb{R}^3$ of $n$ vertices, where "random" could follow any one of a number of models: (1) the convex hull of $n$ points randomly and uniformly ...
11
votes
1answer
510 views

Ratio of circumscribed/inscribed $(n{-}1)$-gons

As a discrete analog of the MO question, "Löwner-John Ellipsoid: incribed and circumscribed," I've been wondering what might be the maximum ratio of this quantity? Let $P$ be a convex polygon of $n$ ...
26
votes
2answers
892 views

Bodies of constant width?

In two-dimensional case one can generalize figures of constant width as figures which can rotate in a covex polygon. Here is one example which can be used to drill triangular holes: I would like to ...
4
votes
4answers
985 views

Delaunay triangulations and convex hulls

This is a reference request. I have the impression that those who work in computational geometry are accustomed to the following. You have some locally finite set of sites in $\mathbb{R}^n$ and you ...
6
votes
2answers
213 views

convex polytopes with many faces and edges but few cells and vertices

For a convex polytope $P$ in $\mathbb R^4$, denote by $N_0,N_1,N_2,N_3$ respectively the number of vertices, edges, faces, cells. By Euler's formula, we know $N_0+N_2=N_1+N_3$, which means there is a ...
24
votes
2answers
716 views

chromatic number of the hyperbolic plane

A notorious problem in combinatorics is the following: If we color $\mathbb{R}^2$ so that no pair of points at unit distance get the same color, what is the fewest number of colors required? This ...
7
votes
1answer
207 views

Integer points in dilations of a disk of volume one

The following question is related to When are Ehrhart polynomials polynomials?. For a positive integer $n$, let $i(D,n)$ be the number of integer points in the disk $x^2+y^2\leq n^2/\pi$, so $i(D,n) ...
13
votes
2answers
2k views

How many vertices/edges/faces at most for a convex polyhedron that tiles space?

I wonder if this problem has already been examined before: Consider a convex polyhedron that tiles $\mathbb R^3$. What is the maximum of vertices/edges/faces that such a polyhedron can have? ...
1
vote
1answer
384 views

Combinatorial optimization and graph coloring

I am considering the following problem: (i) Fix $n$ and color the edges of $K_n$ red and blue arbitrarily. (ii) Let $M$ be the set of monochromatic triangles in $K_n$ and define $g:M\rightarrow ...
0
votes
0answers
100 views

Question regarding contiguous forms

I read about contiguous forms in Achill Scürmann's thesis on positive quadratic forms. I am wondering about one aspect of the Voronoi algorithm presented in there, that enumerates all arithmetically ...
1
vote
0answers
137 views

Traversing perfect quadratic forms

I am wondering whether there is an efficient algorithm to traverse all the $N\times N$ perfect quadratic forms $Q$ inside the polyhedron $e_j^T Q e_j \geq 1$, $j = 1\ldots m$, where $e_j$ are some ...
4
votes
0answers
139 views

Slices of Simplices that are Simplices, Reference?

I am trying to find a reference for the following fact. It is elementary and not hard to prove, but I haven't been able to find the question treated anywhere. Let $A$ be an $l\times n$ matrix with ...
2
votes
2answers
363 views

the minimal diameter of a quadrilateral

Let a convex quadrilateral ABCD with perimeter 1,d is the maximum of AB,AC,AD,BC,BD,CD,prove that d is not less than 1/3 we can prove that parallelogram ABCD with perimeter 1,than one of AC,BD is ...
3
votes
0answers
238 views

Coloring $\mathbb{Z}^k$ and a fixed point theorem

This is potentially another approach to this question. I put it as an update there, but perhaps it would be better to post it separately. If we color $\mathbb{Z}^k$ with the $\ell_\infty$ metric in ...
1
vote
3answers
292 views

Enumerating Perfect Lattices

I have a question regarding enumeration of perfect lattices/quadratic forms. In the thesis of Achill Schürmann http://fma2.math.uni-magdeburg.de/~achill/public/habil.pdf there is an algorithm called ...
4
votes
1answer
576 views

Why is the Street nerve of the Gray tensor product $[1]\otimes [1]$ isomorphic to $[1]\times [1]$

Recall that given two strict ω-categories $A$ and $B$, their lax Gray tensor product $A\otimes B$ is sent to the Verity-Gray tensor product of their associated complicial sets ...
6
votes
3answers
253 views

Minimum separating subdivision in Plane

Hi I was thinking about the following problem: Given a planar Graph embedded in the plane and a set of points $P$ contained in the faces (no face contains more than one point) I want to determine ...
23
votes
3answers
663 views

Largest possible volume of the convex hull of a curve of unit length

What is the largest possible volume of the convex hull of an open/closed curve of unit length in $\mathbb{R}^3$?
1
vote
1answer
236 views

Characteristics of locally triangle-free graph

Hi I am given a triangulation $T $ of a set of points $S $ in the plane and a disk $D$ which doesn't contain any triangle. If I now look at the subgraph $G(V,E)$ of $T $ whose vertices are the points ...