# 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.

864 questions
Filter by
Sorted by
Tagged with
37 views

### What tools can show that (possibly irregular) dodecahedra do not fill space?

Here is a fairly natural question: Can three-dimensional space be filled with convex polyhedra of the same incidence structure (if not the same geometry) as the regular dodecahedron, such that four ...
127 views

### A line perpendicular to a tangent curved at both ends

I made a guess two years ago. I have a strong feeling that there is a proof using the fixed point theorem with geometric visualization, but I couldn't do the proof. If you have a simple closed convex ...
223 views

### Number of perpendicular diagonals in any regular polygon

Find the least positive integer n such that there are at least $1000$ unordered pairs of diagonals in a regular polygon with n vertices that intersect at a right angle in the interior of the polygon. ...
177 views

### Counting problem about polygon triangulations

I have the following question about triangulations (by non-intersecting diagonals, and edges) of regular polygons. What is the number of triangulations of a regular n-gon, up to all symmetry (i.e. the ...
1 vote
17 views

148 views

### In what sense is the sphere the limit of convex polyhedra?

It seems intuitively clear that the sphere can be approximated (both in surface area, but also in a more geometric sense) by certain classes of polyhedra. Do there exist any good formalizations of ...
67 views

### Determine if you are inside or outside a closed region

You wake up in a desert and you find yourself next to a very, very long wall. All you know is that the wall forms a closed region. You are only allowed to walk in the space, and to put "flags&...
142 views

### Number of rectangles generated by $n$ points in the plane

This sounds like a problem that would have been definitely studied by some paper, and to defend myself I have searched using various tools for some time to no avail. What is the configuration of $n$ ... 13 views

### If two combinatorial polytopes have a subset of their cocircuits in common, will they have a triangulation in common?

In "Triangulations" by Loera, Rambau, and Santos, there is a Corollary (4.1.44) that states that two combinatorially equivalent (having the same oriented matroid) point configurations have ...
65 views

### Maximum area of a lattice triangle with 1 interior lattice point

The original problem I had was constructing a conjecture about the number of boundary points on a lattice triangle with 1 interior lattice point. Using Pick's theorem, I have simplified this problem ...
1 vote
70 views

1 vote
70 views

### Making triangles with no common side from a polygon.

How many triangles can be formed by joining vertices of polygon such that no two triangles share a common side? I tried small cases $n=3,4: 1 ; n=5,6: 2$ I first tried to calculate number of ...
62 views

### Maximum number of concave quadrilaterals in n points in regular position

Consider N points in a plane. What is the maximum number of quadrilaterals that are concave? The minimum is always zero: form a convex polygon with all N points, and no 4 of the N will form a concave ...
### Prove that the VC Dimension of Rotatable Squares in a Plane is $5$.
Pre-S: There is a counter example of 6 points! this problem is solved! Prove that the VC dimension of rotatable squares in a plane is $5$. Also, please look at the alternate statement below if not ...
This is a question from the book lectures on Discrete Geometry: Let $C_1, \dots, C_n$ be convex sets in the plane such that each 4-tuple of them contains a ray in the intersection. Prove that $\... 0 votes 1 answer 28 views ### K-Locality of Hilbert curve Let$H: [0,1] \to [0,1]\times[0,1]$be the Hilbert curve (the limit of the family of functions defined on this page ) This curve is well known for its "good locality propreties" Meaning that ... 3 votes 1 answer 65 views ### Combinatorial decomposition of summands in product Let $$X=\{(i_1,\ldots,i_{n-1}) : i_j\in[1,n]\}.$$ Is there a "natural" way to decompose$X=\bigcup_kX_k$such that for$x\in X_k$, no coordinate of$x$is equal to$k$? For example: [$n=2$... 2 votes 1 answer 118 views ### Vertex minors of paths (Vertex Minor) A graph H is a vertex minor of G if H can be obtained from G by a sequence of vertex deletions and local complementation (Local complementation) A local complementation$\tau_v$is a ... 3 votes 1 answer 35 views ### Pinning evenly fragmented papers Draw traces along two identical papers arbitrarily so that each one is divided into$k$parts of the same size. Place$k\$ pins through them with their boundaries coincided. Show that there exists a ... 