The combinatorial-geometry tag has no wiki summary.
2
votes
2answers
101 views
Proving non-convexity of a set of lattice points
I have a set of lattice points S in R^n (listed in memory in a computer for n=8 say). I want to computationally certify that they do not form the lattice points of a convex polytope P in R^n. (Ex. ...
9
votes
1answer
147 views
Which values can attain the minimum solid angle in a simplex
Given a simplex $S$ with a vertex $v$ by the solid angle at this vertex I mean the value $\hbox{vol}(B \cap S)/\hbox{vol}(B)$ where $B$ is a small enough ball centered at $v$ (for example, in the ...
4
votes
1answer
320 views
Difference Sets
Suppose
$$
P \subseteq \{1,2,\dots,N\},\quad |P| = K
$$
We calculate the differences as: $$d=p_i-p_j\mod N,\quad i\ne j$$
Now let $a_d$ denote the number of occurrence of $d$ (for $d = 1, 2, \dots , N ...
2
votes
0answers
76 views
What are the Voronoi cones in 4 variables?
Question: What are the top dimensional cones of the 2nd Voronoi decomposition of the space of positive definite forms in $4$ variables?
The 2nd Voronoi decomposition of the cone of positive definite ...
5
votes
1answer
221 views
When is a 0-1 matrix a one-intersection incidence matrix?
The following problem is what motivated my previous MO question.
It is easily seen that for any given 0-1 matrix $M$, one can always find
a set $\mathcal P$ of points, and a set $\mathcal C$ of ...
1
vote
1answer
86 views
Deducing Linear Inequalities
Let $X_1,X_2,\ldots,X_n $ be indeterminates. Denote by $S$ the set of all linear inequalities of the form
$X_{i_1}+X_{i_2}+\ldots+X_{i_k} \geq k,$
with $k \in \{ 1,2,\ldots,n \}$ and $1 \leq i_1< ...
13
votes
2answers
182 views
Integer lattice points on a hypersphere
Is the following statement true?
For every integer $n\ge2$ and every integer $k\ge0$ there exists a hypersphere in $\mathbb{R}^n$ (circle, sphere etc) containing exactly $k$ integer lattice ...
3
votes
0answers
75 views
pavings and quadratic forms
Hi,
let $L$ be a lattice isomorphic to $\mathbb{Z}^r$ for some positive integer $r$ and $E=L\otimes \mathbb{R}$.
An integral paving in $E$ is a set $\Sigma$ of integral polytopes (the vertices are ...
10
votes
1answer
192 views
Fano plane drawings: embedding PG(2,2) into the real plane
By a drawing of the Fano plane I mean a system of seven simple curves and
seven points in the real plane such that
every point lies on exactly three curves, and every curve contains
exactly three ...
7
votes
0answers
119 views
Maximum number of Vertices of Hypercube covered by Ball of radius R
Let $R>0$ be given and let $H^n$ be the unit hypercube in $\mathbb{R}^n$. The problem I am facing is to find the maximum number of vertices of $H^n$ which can be covered by a closed $n$-dimensional ...
1
vote
0answers
68 views
Realizability of extensions of a free oriented matroid by an independent set
Question:
I am searching for a non-realizable matroid with few dependencies relative to the number of points. Precisely, I would like to find a non-realizable (over $\mathbb{R}$) oriented matroid $M$ ...
13
votes
1answer
211 views
Does every convex polyhedron have a combinatorially isomorphic counterpart whose all faces have rational areas?
Does every convex polyhedron have a combinatorially isomorphic counterpart whose faces all have rational areas?
Does every convex polyhedron have a combinatorially isomorphic counterpart whose edges ...
2
votes
1answer
134 views
The Cayley Menger Theorem and integer matrices with row sum 2
I just filled a gap in my education by learning about the Cayley-Menger theorem, and the Cayley-Menger determinant:
If $P_0, \dots, P_n$ are $n+1$ point in $\mathbb{R}^n$, and $d_{i,j} = |P_i - P_j|$ ...
2
votes
0answers
59 views
rigidity of isoradial graphs
Suppose given a $1$-separated net $\Gamma\subset\mathbb R^2$. Is it true or false that there exists $\delta>0$ and a $\delta$-isoradial graph containing $\Gamma$ as a subset of its vertices?
(I am ...
4
votes
3answers
197 views
Perimeter/Neighborhood of a graph on grid
Hello,
I have a $\sqrt{n}\times\sqrt{n}$ lattice graph $G=(V,E)$ i.e. vertices on said 2-dim integer lattice, and two vertices have an edge if their $L_1$ distance is one.
Now I want to claim ...
2
votes
3answers
220 views
Strong notions of general position
Hi!
I am looking for notions of general position that are stronger than linear general position.
To illustrate, 3 points in linear general position don't lie on a line. I want a notion that would ...
1
vote
0answers
83 views
2d bin packing problem, with opportunity to optimize the size of the bin
I have been tasked with optimizing a manufacturing process. It is a non-trivial, NP hard problem. The problem is similar to the 2d bin packing problem, but we are trying to optimize the size of the ...
11
votes
2answers
671 views
Access to a preprint by D. N. Verma
Some work I am doing is connected with a sequence 1, 3, 40, 1225, 67956, $\dots$ which agrees with http://oeis.org/A012250 for all eight terms. The only useful information in OEIS on this sequence is ...
3
votes
1answer
141 views
What properties does generalized Delaunay triangulation have?
Suppose that instead of the usual circle, we pick some other convex set D and make the Delaunay triangulation of a finite planar point set with respect to this set, i.e. connect two points if there is ...
2
votes
1answer
202 views
Ways to look at a polyhedral graph
Motivation
There are at least three interpretations of an abstract polyhedral (= planar 3-vertex-connected) graph:
the 1-skeleton of a convex polyhedron (when embedded into $\mathbb{R}^3$)
a ...
2
votes
2answers
178 views
Is there a combinatorial analogue of the Kazdan Warner theorem?
First let me state a result of Kazdan and Warner
Let $M$ be a compact orientable two dimensional manifold.
Let $f:M \rightarrow \mathbb{R}$ be a function that has the same
sign as the Euler ...
12
votes
1answer
459 views
Can one recover the smooth Gauss Bonnet theorem form the combinatorial Gauss Bonnet theorem as an appropriate limit?
First let me state two known theorems
Theorem 1 (for smooth manifolds): Let $(M,g)$ be a smooth compact two dimensional Riemannian
manifold. Then
$$ \int \frac{K}{2 \pi} dA = \chi (M) $$
where ...
8
votes
2answers
538 views
A Problem about partitioning $S^2$
Question: Can the 2-dimensional sphere $S^2$ be partitioned into four nonempty sets such that every circle in $S^2$ passes through just three of these four sets?
Here, "just three" means "exactly ...
20
votes
1answer
521 views
Sane bound on number of moves for Maker-Breaker game on $\mathbb R^2$ for $\{0,1,2,3,4\}$
The description below comes from
József Beck. Combinatorial games. Tic-tac-toe theory, Encyclopedia of Mathematics and its Applications, 114. Cambridge University Press, Cambridge, 2008, MR2402857 ...
2
votes
2answers
219 views
What is the smallest number of subsets in such a subdivision?
Given any $30$ points in the plane, what is the smallest number of
subsets in a subdivision of the set of $30$ points into subsets such
that all the points in each subset are on the boundary of the ...
0
votes
1answer
195 views
Is this bounded?
May be better to ask for help here. Let $v_{1}$, $v_{2}$, $\ldots$, $v_{m}$ be the vertices of a
convex polygon in the plane and $v_{m+1}$ be a vertex in the interior
of the convex polygon. Connect ...
9
votes
2answers
278 views
On well separated point sets in the plane
Let us say that a finite set $A$ in the plane is $1$-separated if:
1) it has an even number of points;
2) no open ball of diameter $1$ contains more than $|A|/2$ points.
For a $1$-separated set $A$ ...
1
vote
0answers
113 views
Lattice-point enumeration question involving linear combinations of matrices
I would like to know some references to learn more about an answer to this question, if there are any references:
Let $A_1, \dots , A_m$ and $B$ be $n\times n$ symmetric matrices. Let $$S = \{(x_1, ...
10
votes
0answers
330 views
Reciprocity (Ehrhart-style) for real polytopes?
Is there some sense in which the well-known Ehrhart reciprocity law for rational, convex, polytopes can be extended to any convex polytope with arbitrary real vertices?
In other words, given any ...
4
votes
2answers
244 views
Realization spaces for regular convex polytopes
Q1.
Are there convex polytopes combinatorially equivalent to each of the regular polytopes
that are realized with integer vertex coordinates?
...
0
votes
0answers
120 views
Identify all of the non-overlapping rectangular regions of a simple concave polygon
I am looking for an algorithm to identify all of the rectangles bounded by two parallel edges of a polygon. The rectangle must remain inside of the polygon at all times. My polygon is simple and will ...
4
votes
1answer
901 views
Get Largest Inscribed Rectangle of a Concave Polygon
I'm looking for an algorithm to find a set of largest inscribed rectangles of a concave polygon where each rectangle must be collinear with one of the edges of the polygon.
In other words, I want to ...
6
votes
2answers
767 views
Covering a Polygon with Rectangles
I am tyring to cover a simple concave polygon with a minimum rectangles. My rectangles can be any length, but they have maximum widths, and the polygon will never have an acute angle.
I thought about ...
5
votes
0answers
271 views
$n$ lines in a general position and the number of empty triangles
Question. Consider $n \geq 5$ lines in a general position (i.e. no two lines are parallel and no triple intersections are allowed) in $\mathbb{R}^2$. Let $T(n)$ denote the maximal number of empty ...
3
votes
2answers
306 views
What collections of convex sets result in non-trivial uses of Helly's theorem?
Consider Helly Theorem, taken from notes by Igor Pak:
Let $X_1, \dots, X_n \in {\mathbb{R}}^2$ be convex regions in the plane such that any triple interesects $X_i \cap X_j \cap X_k \neq 0$. Then ...
6
votes
4answers
447 views
Knot diagrams, sets of moves and equivalence relations
Short version: Does anyone study equivalence classes generated by a given set of "moves" (in the sense of, but not limited to, Reidemeister moves) on the set of knot diagrams?
Yes, I understand that ...
4
votes
0answers
131 views
Mean number of $n$-simplices per $(n-2)$-simplex in a triangulated $n$-manifold
Work by Tamura (extending results by Luo and Stong) shows the following.
Theorem: For any closed 3-manifold $M$ and any rational number $4.5 < r < 6$ there is a triangulation $T$ of $M$ for ...
14
votes
0answers
346 views
Monomer-Dimer tatami tilings need better relationships with other math. Summary of results.
A monomer-dimer tiling of a rectangular grid with $r$ rows and $c$ columns satisfies the \emph{tatami} condition if no four tiles meet at any point. (or you can think of it as the removal of a ...
0
votes
1answer
75 views
When do there exist locally regular embeddings of regular graphs?
I don't know how one can tackle the following kind of question, so any hint is welcome. I formulate a precise question in order to fix ideas, but it is to be considered as an example out of a more ...
2
votes
1answer
109 views
Graph implemened into the plane with segments as edges and we search for matching with no edges intersecting
There are some points in the plane and some of them are connected with segments between them. We look at this structure as a graph implemented into the plane where the points are the vertices and the ...
3
votes
2answers
154 views
Generators of a 2D lattice
Dear MO_World,
I'm hoping someone can point me towards a reference for something. I have an invertible $2\times 2$ matrix, $A$, with real entries such that for both of the rows, the entries are ...
13
votes
3answers
484 views
Combinatorial analogues of curvature
There appear to be many "combinatorial" definitions of curvature as applied to finite simplicial (or regular CW) complexes. For instance, we have the ideas of Cheeger, Muller and Schrader, of Forman ...
12
votes
1answer
396 views
Partitioning the vertices of an n-cube with random hyperplane cuts
An evolutionary biologist asked me a question which boils down, at least in part, to what seems to me an interesting question of combinatorial/probabilistic geometry.
It is an old chestnut of a ...
3
votes
1answer
246 views
Grading a non-graded poset as squeezed as possible
Here is a curiosity question (motivated by the recent revamp of ranked-poset routines in Sage).
Let $P$ be a finite poset. We look for a family $\left(a_p\right)_{p\in P}$ of real numbers summing up ...
2
votes
0answers
115 views
A relation on triplets of points in the plane
This question is a follow up of my previous one (Planar sets closed under intersection of circles, Planar sets closed under intersection of circles) and is motivated by G. Zaimi's answer ...
1
vote
1answer
100 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
254 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 ...
39
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
278 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 ...
0
votes
1answer
313 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 ...
