Tagged Questions

The tag has no wiki summary.

174 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 ...
231 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 ...
194 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 ...
934 views

Can one recover the smooth Gauss Bonnet theorem from 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 $K$ ...
549 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 ...
593 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 ...
223 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 ...
207 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 ...
321 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$ ...
134 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, ...
346 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 ...
272 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? ...
1k 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 ...
1k 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 ...
293 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 ...
325 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 ...
490 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 ...
166 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 ...
426 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 ...
79 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 ...
115 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 ...
175 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 ...
547 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 ...
442 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 ...
253 views

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 ...
124 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 ...
107 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 ...
281 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 ...
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 ...
292 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 ...
333 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 ...
272 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 ...
849 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 ...
395 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, ...
595 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 ...
209 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 ...
824 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 ...
204 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 ...
200 views

96 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 ...
135 views

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 ...
136 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 ...
352 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 ...
273 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 ...
495 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 ...
436 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$?
Is there a known algorithm which, given a finite multiset (unordered list) of integers $A$, returns a yes/no answer for ...
Let $V_n$ be the least real number such that for every convex subset of $\mathbb{R}^n$ with hypervolume $1$ there is a containing simplex with hypervolume $V_n$. What is known about $V_n$? Is there a ...