Questions tagged [combinatorial-geometry]

Combinatorial geometry is concerned with combinatorial properties and constructive methods of discrete geometric objects. Questions on this topic are on packing, covering, coloring, folding, symmetry, tiling, partitioning, decomposition, and illumination problems.

548 questions
185 views

Largest number of sides and diagonals

I have asked to solve the following: For given an integer number $n\ge3$, find the largest positive number $k_n$ for which: for every convex $n-$polygon (with $n$ sides), we can find $k_n$ segments, ...
105 views

What is the connection between these quantities?

$S = 6,15,20,15,6,1$ is a row of Pascal's triangle with its left-hand edge removed. What is the relationship between $S$, the number of m-faces of a regular n-simplex, and states of a finite quantum ...
442 views

Venn diagram with rectangles: How many among $\binom{n}{k}$ regions created by intersections of exactly $k$ rectangles can be represented?

This question is related to the question I asked a few time ago, see Venn diagram with rectangles for $n>3$. Within this question I wanted to know whether it is possible to draw a Venn diagram with ...
84 views

How can I count the number of square on this sphere?

I have a sphere has equation $$(x-2)^2+(y-4)^2+(z-6)^2 = 225.$$ Now I want to count all squares on this sphere with the following condition: All vertices of four point are 12 different integeral ...
31 views

Defining the “Level of Convexity” for Non-Convex Bodies

The definition of convexity for a body in $\mathbb{R}^n$ is simple enough, namely: a body $K\subset \mathbb{R}^n$ is convex if for any two points $x,y\in K$ the line segment between $x$ and $y$ is ...
190 views

$0$ interior to the convex hull of rational vectors

Reading a paper by John Franks, at a certain point it is proven that $0$ is in the interior of the convex hull of $v_1, v_2, v_3, v_4$, where the $v_j$ are certain vectors in the plane with rational ...
580 views

Venn diagram with rectangles for $n > 3$

Is it possible to draw a Venn diagram with rectangles for $n > 3$? If yes, is it possible for all $n\in\mathbb{N}$? If no, up to which $n$ is it possible? Furthermore, the rectangles should have ...
231 views

How many ways are there to traverse a 3 by 3 grid such that you start at (0,0) and end at (2,2)?

How many ways are there to traverse an $n$ by $n$ grid such that you start at $(0,0)$ and end at $(n-1,n-1)$ given these conditions: 1)You can traverse each branch at most one time. 2)You can pass ...
644 views

Prove that the shortest side of one triangle is the longest side of another, given 3 pairs of points.

I have received this question and am having great difficulties. I don't even know how to try to solve it. It goes like this: 6 points are given in a room. These points are pairwise differently ...
30 views

Cases of quasi-coincident “almost orthogonal” projections of n-dimenstional polytopes in (n-k)-spaces

Background: In Regular Polytopes, Coxeter shows that the familiar 3-dimensional rhombic dodecahedron resulting from a true orthogonal projection of the 4-cube has a "floor-plan" which is the same as ...
39 views

Are the roots of E6 in 9-space ever treated as an orthogonal projection of a set of points in 11-space?

Background: For the coordinates of the symmetric representation of the roots of E6 in 9-space, see section "Roots of E6" here: https://en.wikipedia.org/wiki/E6_(mathematics) Question: Are the ...
44 views

192 views

Cases where ANY 2 of 3 +/- choices select one of four possible elements

Edited 1/21/2018 to add the following: Here is a DropBox link https://www.dropbox.com/s/7rtt0iqmgimsgzu/Zumkeller_edge-magic.pdf?dl=0 to a PDF showing how my team used biomolecular first ...
45 views

Can you determine set of points from their point-to-point vectors?

Let P be set of points in $R^3$. Given all possible point-to-point vectors $V=\{u-v : u,v\in P \}$ can you determine P up-to translation and rotation? Anyone know thereoms for similar problems? ...
98 views

Distribution of all point to point distances on a square $L \times L$ lattice?

Is it possible to derive a probability density function $P(d,L)$ which gives probability of having a point to point distance $d$ on a $2D$ square lattice of size $L$ or at least it's asymptotic ...
183 views

Hadwiger–Nelson problem 5 colors needed if color sets are Lesbeauge measureable

Where can I find a reference to the result that if the plane is colored in 4 colors, so that the set of colors of the same kind is measurable for each color, then there is a set containing 2 of ...
56 views

Listing the elements of a covering for a closed disk by open disks

This problem is somewhat related to some homework I had recently. However, as stated, I don't know if a solution yet exists. I asked some friends and some of my professors, but none of them know how ...
506 views

On existence of boards that be covered by every free tetromino

There is a board which can be covered by each of five free tetrominoes: However, it's not simply-connected (has a hole). I wonder if there is a simply-connected board with the same property.
377 views

The central ideas in Hales's proof of the Honeycomb conjecture.

I have been trying to understand Thomas Hales's proof of the honeycomb conjecture: https://arxiv.org/pdf/math/9906042.pdf However, despite the fact that the paper is clearly written, I find myself ...
101 views

$2n+1$ segments on a line

$2n+1$ segments are marked on a line. Each of these segments intersects at least $n$ other segments. Prove that one of these segments intersects all other segments.
32 views

Optimal algorithm of a separating hyperplane

What is an optimal algorithm for finding a separating hyperplane of two nonintersecting convex hulls of two sets of finite number of points?
Given two circles with the radius of $1$, two circles with a radius of $2$ and two coins of the radius $3$. It is allowed to put two of them so these circles would touch each other.. Then the circles ...