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.

learn more… | top users | synonyms

0
votes
0answers
13 views

Width of a cone

Let $V=\{v_k\}$ be a collection of vectors of $\Bbb{R}^n$, and define their cone to be the set of all their non-negative linear combinations: $$ C(V):=\Big\{ \sum_k a_k\,v_k; \; a_k\ge 0 \Big\}\;. $$ ...
1
vote
0answers
28 views

Using the general ham sandwich theorem to proof Hobby-Rice

Matousek mentions that you can proof the continuous necklace theorem known as Hobby-Rice theorem via the continuous ham sandwich theorem. The continuous ham sandwich states: Let $\mu_1,\mu_2,...,\...
1
vote
1answer
32 views

Polyhedron, understanding face vs facet.

I've the two following definitions, for which I was trying to understand the difference. For a given polyhedron $P$ a face $F$ is both $P$ itself or the intersection of $F$ with $P$. A facet is ...
0
votes
1answer
41 views

What is the minimum number of vertices needed to create n non-overlapping triangles

How can I calculate the minimum number of vertices needed to draw $n$ non-overlapping triangles? That is, the interiors of triangles are disjoint (equiv. the triangles disjoint except possible along ...
2
votes
1answer
41 views

Understanding definition of “dimension” of a subset of $\mathbb{R}^n$

In a book of combinatorial optimization the following definition is stated: A polyhedron in $\mathbb{R}^n$ is a set of type $P = \left\{x \in \mathbb{R}^n \;:\; Ax \leq b \right\}$ for some matrix ...
0
votes
1answer
39 views

More than 3 branch point Dessign d' enfant

I wanted read about Dessign d' enfants most of the reference define it as (X,D) where X is compact orientable surface and D is the bipartite graph with some properties that is there is a bijection ...
4
votes
0answers
58 views

Minimum number of points chosen from an N by N grid to guarantee a rectangle?

What is the maximum number of points that can be chosen from an $N$ by $N$ grid such that no $4$ of the chosen points form a rectangle with sides parallel to the axes of the grid? Equivalently, what ...
0
votes
0answers
30 views

How to distribute points on a sphere with maximum uniformity

This question is inspired by projects like the National Ignition Facility (NIF), which have to arrange a fixed number of points on a sphere in as uniform a way as possible. In NIF's case, the points ...
2
votes
1answer
37 views

Pack balls with maximum sum of radii

We pack $8$ balls into a cube of side length $1$ so that no two balls share an interior point. what is the maximum sum of the radii of the balls? It is possible to pack $8$ balls or radius $1/4$, ...
9
votes
0answers
130 views

Surface of the intersection of $n$ balls

Suppose there are $n$ balls (possibly, of different sizes) in $\mathbb R^3$ such that their intersection $\mathfrak C$ is non-empty and has a positive volume (i.e. is not a single point). Apparently, $...
0
votes
1answer
61 views

What is the number of interior faces adjacent to an interior vertex in a triangulation in $\mathbb{R}^3$?

Let $\Omega$ be a polygonal domain in $\mathbb{R}^3$. Assume $\Omega$ is partitioned into tetrahedra using the most common admissible triangulation, that is, roughly speaking, two adjacent tetrahedra ...
2
votes
2answers
19 views

Monochromatic congruent triangles on a 10-gon

Five vertices of a regular $10$-gon are painted red and five blue. Prove that there will always be two congruent monochromatic triangles. Please tell me if my proof is acceptable. I don't know how ...
0
votes
1answer
27 views

Can any connected graph of $\ge k$ nodes be partitioned into $k$ components?

Dyer and Frieze in "ON THE COMPLEXITY OF PARTITIONING INTO CONNECTED SUBGRAPHS" showed that the problem of deciding whether a planar graph has a connected-$k$-partition is NP-complete. On a graph ...
0
votes
1answer
22 views

Monochromatic triangle similar to a given triangle

Given a scalene triangle, $A$ and $B$ play a game. Each move, $A$ chooses a point on the plane, and $B$ colors it red or green. If three points of the same color form a triangle similar to the ...
6
votes
1answer
115 views

Combinatorics problem involving n-dimensional space

Consider a set of more than $\frac {2^{n+1}} {n}$ points $(n>2)$, chosen from the $2^n$ points of the $n$-dimensional space which have the coordinates $\{ \pm1, \pm1, ..., \pm1 \}$. Show that ...
5
votes
1answer
48 views

Plane tesselation, using stairs $n\times n$, is it possible?

The other day I was constructing new mathematical problems for my pupils and thought of something like this: Given the infinite sequence of "stairs" $n\times n$, constructed from $1\times1$ ...
2
votes
0answers
18 views

Number of simplices of convex hull of points on a $d$-sphere.

I was discussing this with my professor the other day and he left me to figure out. And I can't for the life of me, figure out why this is so. I would appreciate what I should look into rather than an ...
0
votes
1answer
28 views

Combinatorial Geometry explanation

I do not understand what is going on in $(4)$: for every flat $E \in \mathcal F$, $E \ne X$, the flats that cover $E$ in $\mathcal F$ partition the remaining parts. What is meant by "the flats ...
5
votes
1answer
48 views

Maximum number of right-angled triangles

Let $S$ be a set of $n$ points in the plane, no $3$ collinear. Determine the maximum number of right-angled triangles with all three vertices as points in $S$. This is a slightly more difficult and ...
1
vote
1answer
99 views

Circumscribed Simple Line Arrangements Have Hamiltonian Circuits?

An arrangement of $s$ lines are drawn in the plane so that no three lines intersect at a common point and no two lines are parallel. Now circumscribe this arrangement by a circle so that all ...
1
vote
0answers
9 views

Projection onto a symplex

Suppose we have $n$ vectors in an $m$-dimensional vector space such that their span is all the space and none of them are zero. We choose any hyperplane which does not pass through zero and project ...
0
votes
0answers
16 views

Two polylines could form a convex quadrilateral

A close polyline $\Delta$ with length $n$ here means a sequence of segments $A_1A_2,\ldots, A_{n-1}A_n$ and $A_nA_1$ so that there are no two segments $A_iA_{i+1}$ and $A_jA_{j+1}$, with $1\leq i,j\...
1
vote
0answers
101 views

Circumscribed simple line arrangements are 3-colourable?

An arrangement of $s$ lines are drawn in the euclidean plane so that no three lines intersect at a common point and no two lines are parallel. Now circumscribe this arrangement by a circle so that all ...
3
votes
0answers
26 views

Hypercube subdivision for a combinatorial problem

I have to design a combinatorial algorithm based on some simmetries of an hypercube and I'm pretty sure such a problem has already been studied. Let's start with a 3D case. Consider a cube like the ...
0
votes
0answers
12 views

lower bound for the length of the longest path contained in a subset of $\mathbb{Z}^d$

Let $A \subset \mathbb{Z}^d$ be a finte connected set. Let $\gamma$ be the longest self-avoiding path of nearest neighbors which is entirely contained in $A$. Can you provide a lower bound for the ...
0
votes
0answers
11 views

Minimal diameter of a connected subset of $\mathbb{Z}^d$

Let $A \subset \mathbb{Z}^d$ be a connected set of cardinality $|A|$. Let the diameter of the $A$ be defined as the length of the longest path of distinct, nearest neighbor sites which is entirely ...
1
vote
1answer
44 views

Height of $n$-simplex

$n$-simplex is a generalization of triangle or tetrahedron (with $n + 1$ vertices). The problem is to find its height. I kindly ask to check my solution. I am not fluent with $n$-dimensional space ...
9
votes
1answer
203 views

Obscuring squares of Rubik's cube

This is a combinatorial question related to Rubik's cube $3\times3\times3$ (and, in the end, its generalizations $n\times n\times n$). I assume that the readers are familiar with this puzzle. Let's ...
1
vote
1answer
41 views

Maximizing the volume of the convex hull of $N$ points in the unit ball

Suppose we are given an integer $N\ge4$, and we have to pick $N$ points in a unit ball in $\mathbb R^3$ to maximize the volume of their convex hull. Are those points necessarily on the surface of the ...
4
votes
2answers
140 views

Maximum distance between points in a triangle

An equilateral triangle has sides of unit length. a)Show that if five points lie in/on the triangle, then at least two of the points lie no farther than 0.5 units apart. b)Show that 0.5 cannot be ...
0
votes
0answers
29 views

Sufficient conditions to decompose a graph into pair-wise edge disjoint cycles?

Are there any conditions which will guarantee that for a graph $G$ of sive $v$, we could cut edges in such a way that what we're left with is a graph of $v/n$ disconnected components, where each ...
1
vote
0answers
37 views

A generalization of a geometry Olympiad problem involving $kn$ colored lines and a circle.

Let $n$ and $k$ be positive integers. Let $L$ be any set of $kn$ lines in the plane, no two of which are parallel. Each line in $L$ is colored one of $k$ colors, and there are $n$ lines of each color. ...
1
vote
1answer
51 views

Number of balls covering a $n$-dimensional sphere [closed]

What upper bounds for number of covering a unit sphere balls with a same radius $r$ and centers on this sphere are known?
3
votes
1answer
59 views

An upper bound on the sum of the lengths of chords

Problem: Several chords are drawn in a circle of radius $1$, and each diameter of the circle intersects no more than four of them. Prove that the sum of their lengths does not exceed 13. I couldn't ...
1
vote
1answer
46 views

Given two sets of points in the plane, there exists a point with equal sum of distances to the points in each set

Let ${A_1, ..., A_n}$ and ${B_1, ..., B_n}$ be two given sets of points in a plane with different centroids. Prove that there exists a point $P$ in the plane such that $\sum |PA_i| = \sum |PB_i|$. ...
4
votes
1answer
73 views

Combinatorially equivalent polyhedron with vertices from a given dense set

In this question we are only interested in convex polyhedra in the Euclidean space $\mathbb R^3$. Polyhedra $P$ and $P'$ are said to be combinatorially equivalent iff there is a bijection between ...
1
vote
1answer
33 views

Scalene rectangulation of a square: let me count the ways

A rectangulation of a square is a dissection of the square $S$ into smaller rectangles $R_i$, $i=1,\ldots,n$ with the usual caveats: $S = \cup_i R_i$ and the interiors of distinct rectangles $R_i,R_j$...
2
votes
0answers
46 views

A circle can include all but one of n points, but which one can it be?

The answers to the question "Circle enclosing all but one of n points" demonstrate that, given $n$ points, it is possible to construct a circle such that all but one of the points is inside the circle ...
19
votes
6answers
739 views

Circle enclosing all but one of $n$ points

It looks like a simple question but it turns out rather difficult to me. Here is the question: Given $n$ points on the plane, can we always draw a circle that includes exactly $n-1$ of them?
1
vote
0answers
35 views

On partitioning a finite set of points in the plane by drawing a line

Number of ways to separate $n$ points in the plane The linked answer was to this question: Suppose you have $n$ points in the plane, no three of which are colinear. How do you show that the number ...
0
votes
0answers
6 views

Arrangement of Convex Discs in the plane is independent of the choice of origin?

This is the Problem 3.1 in 'Combinatorial Geometry' by J. Pach, and P. Agarwal. Problem: Prove that if C is any arrangement of convex discs in the plane, then $\bar{d}$$(C,\mathbb{R}^2)$ and $\...
1
vote
0answers
8 views

Number of translated cubes covering a given hypercube in $\mathbb{R}^n$

Let $\Omega \subset \mathbb{R}^n$ be open and bounded, and let $Q \subset \Omega$ be a hypercube. Furthermore, denote by $D$ the $n$-dimensional unit cube $(0,1)^n$. Let $k \in \mathbb{N}$ be big, i....
0
votes
1answer
44 views

Barycentric subdivisions and labeling of $(d-1)$-simplex

I am trying to prove that it is always possible to label the vertices of the $k$-th barycentric subdivision of a $(d −1)$-dimensional simplex with labels $1, 2, . . . , d$ such that each simplex ...
1
vote
0answers
37 views

Given $5$ points on a sphere, divide the surface into $5$ congruent connected regions containing one point.

There are $5$ points on the surface of a sphere. Is it always possible to divide the surface into $5$ connected congruent regions such that each region contains one of the $5$ points?
2
votes
0answers
24 views

Triangulations of combinatorially equivalent polytopes

I am wondering which relation(s) there are between triangulations of combinatorially equivalent polytopes that use no new points: Let $P,Q$ be a $n$-polytopes such that their face lattices are ...
2
votes
0answers
23 views

Hexagons share interior points

Can we draw infinitely many hexagons, not necessarily convex, on the plane so that any three of them share a common interior point, but no four of them does? For four hexagons this is possible, using ...
6
votes
2answers
435 views

Positivity of the alternating sum associated to at most five subspaces

Let $V_1 , V_2 , \dots , V_n $ be vector subspaces of $ \mathbb{C}^m$ and let $$\alpha = \sum_{r=1}^n (-1)^{r+1} \sum_{ \ i_1 < i_2 < \cdots < i_r } \dim(V_{i_1} \cap \cdots \cap V_{i_r})$$ ...
1
vote
0answers
54 views

Variation of the opaque forest problem (a.k.a farmyard problem)

I was wondering about the following variation of the opaque forest problem (see here and there for previous questions) : What is the least length set of segments that will intersect every straight ...
1
vote
0answers
25 views

Projection of hyper-cubes via multiple variable elimination

I am not a mathematician but I do use some tools from geometry in robotics. So, I apologize if what I am writing here is not mathematically consistent but I really do need your help. I have a linear ...
1
vote
2answers
182 views

Similar Triangles in Tiling a Plane

When tiling the infinite plane with triangles, is it necessary for two of the triangles to be similar? I've tried different methods to construct, but none work. My idea was to use right triangles to ...