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

7
votes
3answers
135 views

Maximum area of triangle inside a convex polygon

Prove that within any convex polygon of area $A$, there exists a triangle with area at least $cA$, where $c=\tfrac{3}{8}$. Are there any better constants $c$? I'm not sure how to approach this ...
0
votes
1answer
37 views

Number of Rational Solutions $\mathbf{x}\in[0,1)^n$ to the Matrix Condition $\mathbf{A}\,\mathbf{x}\in\mathbb{Z}^n$

Let $n$ be a positive integer and $\mathbf{A}$ an $n$-by-$n$ matrix with integer entries. Suppose that $k:=\big|\det(\mathbf{A})\big|$ is nonzero. How many $n$-by-$1$ column vectors $\mathbf{x}\in\...
3
votes
3answers
61 views

Prove that there are exactly $k$ pairs $(x,y)$ of rational numbers with $0\leq x,y<1$ for which both $ax+by,cx+dy$ are integers.

Let $a,b,c,d$ are integers such that $(a,b)=(c,d)=1$ and $ad-bc=k>0$. Prove that there are exactly $k$ pairs $(x,y)$ of rational numbers with $0\leq x,y<1$ for which both $ax+by,cx+dy$ are ...
0
votes
1answer
27 views

Transforming a closed polyline to a boundary of convex polygon

Let $\ell$ be a closed polyline on a plane, i.e. $$\ell = \bigcup_{i=1}^n A_iA_{i+1}$$ where $n\ge 3$ is an integer and $A_1, \ldots, A_n$ are points on a plane such that for every $i=1,2,\ldots, n$ ...
0
votes
0answers
15 views

Solve $\max_X \mathrm{sum}(AXB \geq \gamma)$, with $X$ being a permutation matrix

I have a problem to find the best permutation matrix $X \in \{0,1\}^{n \times n}$, which would maximizes the number of elements in $AXB$ which are above a certain positive number $\gamma$. In other ...
0
votes
0answers
18 views

Find permutation matrix $X \in \{0,1\}^{N \times N}$ in order to make $XAX \geq_c B$

I need to solve a problem to find out the best permutation matrix $X \in \{0,1\}^{N \times N}$ which would maximize the number of elements in matrix $XAX$ which are above (component-wise) matrix $B$ ...
0
votes
0answers
13 views

Condition for n points in the plane to determine a convex n gon

Suppose there are n points in the plane, labelled 1 through n, no three of which lie on a line. Suppose further that for every triple [i,j,k] with i< j < k that travelling from i to j to k is ...
1
vote
0answers
27 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
30 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
34 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
45 views

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

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
42 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
32 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
63 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
118 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
49 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
50 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
101 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
104 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
13 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
48 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
45 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 ...
5
votes
2answers
159 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
59 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
35 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
47 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
742 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
39 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
48 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 ...