# Questions tagged [discrete-geometry]

Discrete geometry includes the study of covering, illumination, packing, convex bodies, convex polytopes, and other metric geometry.

735 questions
Filter by
Sorted by
Tagged with
1 vote
30 views
+100

### Number of unit cubes meeting the boundary of a convex set

Suppose $C \subseteq [0,n)^k$ is a convex set, and $\partial C$ is its topological boundary: its closure minus its interior. Is it true that $\partial C$ meets at most $2k n^{k-1}$ unit cubes? By a ...
27 views

• 31
85 views

### Does colinearity in construction with ruller has to occure because we "decide" it in the contruction?

Let $D$ be a set of lines in the real projective plane such that for all $d\in D$, $\bigcap (D\setminus \left\{d\right\})=\emptyset$ and let $Dot(D)$ be the set of all dots that belong to at least two ...
• 351
62 views

### dominant of a polyhedron

On page 8 of this pdf (https://www.lix.polytechnique.fr/~vjost/mpri/prelimILP.pdf) from Schrijvers book "combinatorial optimization" the dominant of a polytope is defined as: P$^\uparrow$ := ...
• 1
14 views

### empty simplicies in the cyclic polytope

I have to proof the following thing: Show that all empty symplices ( i.e a subset of the complex T s.t T is not inside but all the subset are inside T) in the boundary complex of $cyc_{2d}(n)$ have ...
• 293
30 views

• 23
1 vote
119 views

### Is $K_{3,3}$ with vertices on a circle locally rigid in the plane?

Consider the complete bipartite graph $K_{3,3}$ in plane such that all its vertices lie on a circle. Is this framework locally rigid in plane (which I believe is the case) and if so, how to prove this?...
• 10.2k
1 vote
27 views

### Build a rotation matrix to perform discrete parallel transport on a discrete curve

Consider a discrete cuve with vertices $\{...x_{i-1}, x_i, x_{i+1}, ...\}\in \mathbb{R}^{3n}$, and denote the edge $e^i=x_ix_{i+1}$ and tangent $t_i=x_{i+1} - x_i$. When perform discrete parallel ...
47 views

### On point line incidences

Given a set of $n$ points $P_1, \ldots, P_n$ and $n$ lines $L_1, \ldots, L_n$ in $\mathbb{F}^2$, consider the set $I=\{(p_i, L_j)|L_j\text{ contains }p_i\}$ of point line incidences. The famous ...
• 435
270 views

### Number of triangles a point lies in on a plane

On a plane , there are $2n+1$ points where no three points are co-linear. Show that for any point $P$ which is one of the points, the number of triangles the interior of which $P$ lies in is always ...
• 1,219
196 views

### Enumerating the "discrete straight lines" in an $n \times n$ grid.

This question is related to this other question. I would like to write an algorithm to enumerate all subsets of the $n^2$ squares of an $n \times n$ grid such that, for each subset, there exists a ...
• 2,573
32 views

### Counting lattice points in cross-sections of a polytope

Let $P$ be polytope in $\mathbb{R}^d$ with vertices in $\mathbb{Z}^d$ and let $h(z_1,\ldots,z_d)\in\mathbb{Z}[z_1,\ldots,z_d]$ be a degree one polynomial with integer coefficients, thought of as a &...
63 views

### Conformal equivalence of metrics: different definitions in discrete and continuous case

I currently study discrete conformal maps and read the paper "Discrete conformal maps an ideal hyperbolic polyhedra" by Bobenko, Pinkall and Springborn. Consider the following definitions: ...
1 vote
145 views

• 61