# Tagged Questions

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.

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 ...
37 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$, ...
130 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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?
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 ...
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|$. ...
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 ...
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$...
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 ...
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?
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 ...