Questions tagged [discrete-geometry]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
18 views

Upper bound for Pach's Selection Theorem for plane

Pach's Selection Theorem for plane says that: Assume $X \subset \mathbb{R}^{2}$ is a finite set of points in general position, partitioned into three colour classes $C_{1}, C_2, C_3$ with $\left|C_{i}\...
user avatar
  • 685
4 votes
0 answers
54 views

If a polyhedron's faces and vertex figures are convex, is the polyhedron convex?

Suppose a polyhedron's faces are convex polygons, and its vertex figures are convex spherical polygons (or convex cones, depending on definitions). Must the polyhedron be convex? The polyhedron may be ...
user avatar
  • 4,151
0 votes
1 answer
26 views

On the non-sufficiency of total unimodularity of the constraint matrix in the definition of an integer polytope

Crossposted at Operations Research SE Is there an example of an $m\times n$ integer matrix $A$ and an integer vector $b\in \mathbb {Z}^{m}$ such that the polyhedron $P := \{ x\in \mathbb {R}^{n} \mid ...
user avatar
0 votes
0 answers
22 views

Packing & placing rectangles inside a (not-rectilinear) polygon

Intro I have a polygon (not rectilinear) of a fixed size which would act as the container for some number of rectangles. The rectangles are: the same size (height and width) and, they can be rotated ...
user avatar
1 vote
0 answers
40 views

Division of $n$-dimensional simplex [closed]

How many congruent $n$-dimensional simplexes can an $n$-dimensional simplex be divided into? Obviously, a triangle can be divided into $k^2\left(k\in N^*\right)$ congruent triangles (by dividing the ...
user avatar
1 vote
0 answers
39 views

Separation of polyhedra via Farkas' lemma

Let $A\in\mathbb{R}^{m_1\times n}$, $B\in\mathbb{R}^{m_2\times n}$, $a\in\mathbb{R}^{m_1}$, and $b\in\mathbb{R}^{m_2}$. Consider the intersection of an "open" polyhedron and another closed ...
user avatar
1 vote
0 answers
33 views

A question regarding the proof of Lévy–Steinitz theorem

I am reading the proof of Lévy–Steinitz theorem from ON THE POWER OF LINEAR DEPENDENCIES, which asserts that given a finite set $V$ of the unit ball $B$ of any norm(in $\mathbb{R}^d$) such that $\...
user avatar
2 votes
1 answer
135 views

Intersection of convex hulls

I have two polyhedral sets $\mathscr{P}_1, \mathscr{P}_2,$ defined as convex hulls $$\mathscr{P}_1 = \mbox{conv} \left\{ v_{1},\dots, v_{N} \right\}, \qquad \mathscr{P}_2 = \mbox{conv} \left\{ w_{1},\...
user avatar
0 votes
0 answers
22 views

Minimum number of straight line segments in a polygonal chain covering a square lattice

Let $a:={1,2,\cdots,n}$. Consider $A:=a\times a$ square lattice points on $\mathbf Z^2$. We are to draw a polygonal chain consisting of $m$ straight line segments traversing all points in $A$. What is ...
user avatar
  • 8,977
0 votes
0 answers
18 views

How we can determine the number of lattice points on a region dr? For a square and an hexagonal lattice using the exact formula

How we can determine the number of lattice points on a region dr using for a sguare latiice the following formula: (see: http://mathworld.wolfram.com/GausssCircleProblem.html: $$N(r)=1+4\lfloor r \...
user avatar
  • 45
2 votes
0 answers
14 views

Book and study recommendations - discrete geomtry

I am a Computer Science graduate student and my research topic (if you can call it that, since I just started) is discrete geometry. Stuff like Helly's theorem, convex geometry, p-q theorems, epsilon-...
user avatar
  • 312
1 vote
0 answers
38 views

If a line intersects three segments in the plane, then must there be a line through endpoints of two of the segments while intersecting the third?

Assume we are given 3 segments in the plane so that there exists a line intersecting them. Regardless of their disjointness, can we always say that there is a line that is tangent to two of them while ...
user avatar
0 votes
0 answers
91 views

Computing the local curvature on a surface mesh of general topology (polygons)

I am looking for an accurate and robust way of computing the total curvature of a surface mesh that consists of a set of polygonal faces. The total curvature of a surface $\Sigma$ is defined as $\...
user avatar
0 votes
0 answers
20 views

Two definitions about reflexive polytopes

I am working through Computing the Continuous Discretely and they give the definition of a reflexive polytope as $$ P=\{x \in \mathbb{R}^d : Ax \leq 1\}$$ where all entries from $A$ are integers. It's ...
user avatar
1 vote
0 answers
32 views

Special case of Katchalski's result

Given a family of convex sets in the plane. The intersection of any 4 of them contains a ray (so, we are assuming that the cardinality of the family is at least 4). Prove that the intersection of all ...
user avatar
0 votes
0 answers
28 views

Maximum diameter $D$ such that all sets of diameter $D$ is covered by unit disc

Given a unit disc what is the maximum diameter $D$ such that all sets of diameter $D$ is covered by the unit disc? I am quite unfamiliar with results from discrete geometry, but I found a result from ...
user avatar
  • 1
0 votes
0 answers
60 views

How is depending the number of lattice points on the lattice constant in a square and an hexagonal lattice? Exact formula and the approximation

I am trying to determine how many integer lattice points there are in a circle centered at the origin and with radius r in an square and hexagonal lattice. An approximation can be used: $$N(r)=\frac{...
user avatar
  • 45
0 votes
0 answers
13 views

Discrete translation invariant set of points

First a bit of background, is that this problem is related to a radar imaging problem. The linear points below would be a set of receiving antennas. The grid mentioned in this problem would be a set ...
user avatar
  • 1
0 votes
0 answers
29 views

Faces for Polytopes.

We are using the definition for faces, as an intersection with a supporting hyperplane. I have to show, $F$ is a face of polyhedron $Q$, if and only if $F$ is convex and for every $0 < x < 1$, $...
user avatar
1 vote
1 answer
252 views

Minimizing the number of different values of $\frac{f(c)-f(d)}{c-d}$ for integers $c,d$ and polynomial $f$

I am looking for the following quantity $\mathcal{E}:=\min \Big( \#\Big\{ \frac{f(c)-f(d)}{c-d}:\text{$f$ is a polynomial s.t. $\text{deg}(f)\ge 2$}, c,d\in A\subseteq \mathbb{Z}~~\text{and}~~|A|\ge ...
user avatar
2 votes
0 answers
27 views

The number of intersection graphs of $n$ convex sets in the plane is $2^{\Omega(n^2)}$

I'm supposed to show that the number of intersection graphs of $n$ convex sets (or $n$ simple curves) in the plane is at least $2^{\Omega(n^2)}$, but I don't really know how to do this. I know that $2^...
user avatar
  • 309
4 votes
0 answers
94 views

Why are there finitely many of these approximations of $\sqrt{2}$? [duplicate]

I'm solving the following problem from a discrete geometry book (Lectures on Discrete Geometry, Jiri Matousek). Prove that for $\alpha=\sqrt{2}$ there are only finitely many pairs $m,n\in\mathbb{N}$ ...
user avatar
  • 309
-1 votes
1 answer
48 views

On partitioning triangles and pentagons [closed]

Is there any triangle that can be cut into 5 mutually congruent pieces? If the answer is "yes" how does one characterize such triangles? What if we restrict the pieces to be convex? Is ...
user avatar
0 votes
1 answer
45 views

Area gradient, mean curvature normal, and the "cotan formula"

Show that when we take the gradient of the total surface area with respect to the position of one of the vertices, we get $$\nabla_{f_{i}}\sum_{ijk\in F}A_{ijk}=\frac{1}{2}\sum_{ij\in E}\left(\cot\...
user avatar
  • 9,478
1 vote
1 answer
41 views

How do points on a grid satisfy the grid equation?

Currently, I'm working on a presentation regarding Penrose tilings. During my research, I've become interested in the Pentagrid method of construction, that was introduced by N.G. de Bruijn in 1981 (...
user avatar
4 votes
2 answers
72 views

Tucker's lemma, Borsuk-Ulam, triangulating a ball in *truly* antipodally symmetric fashion

I'm attempting to prove Tucker's Lemma from the Borsuk-Ulam theorem by means of the proof sketched as "immediate" on page 36 of Matoušek's Using the Borsuk-Ulam Theorem. In order to do this, ...
user avatar
0 votes
0 answers
36 views

Maximum number of points with mutually distinct views of a set is $O(n^4)$

I'm looking at the following problem from Jiří Matoušek's Lectures on Discrete Geometry: Let $P = \{p_1, p_2,\dots p_n\}$ be a set of $n$ points in the plane. We say that points $x$, $y$ have the same ...
user avatar
  • 309
1 vote
0 answers
25 views

A lower bound for the number of vertices of Voronoi diagram for this set

For a number $n\ge 2$, we define a set of points in $A_{2n}=\{(i,0,0)\in\mathbb{R}^3|1\le i\le n\}\cup\{(0,n,j)\in\mathbb{R}^3|1\le j\le n\}$. What can we say about the number of vertices in the ...
user avatar
  • 309
1 vote
0 answers
34 views

Boundary of a zonotope

I am currently learning about zonotopes but I am having troubles understanding the concept of it. I know that a zonotope is defined as $$\left\lbrace x : x=c +\sum_{i=1}^k \xi_ig_i, \xi_i \in \lbrack -...
user avatar
  • 578
0 votes
1 answer
60 views

What is the expression of mean curvature on a torus?

Let $(x,y,z)$ be the standard Cartesian coordinates of $\mathbb{R}^3$. For a ball of radius $R$ we know its sphere can be represented by the level set $$ x^2 + y^2 + z^2 - R^2 = 0 $$ and the mean ...
user avatar
0 votes
0 answers
10 views

Describe an orthoplex as a polyhedron [duplicate]

How can I define a orthoplex as a polyhedron? The definitions that I am using are: $n$-dimensional orthoplex: $$O_{n} = \mbox{conv}\left\{e_1, -e_1, e_2, -e_2,\dots, e_n, -e_n \right\}$$ where $e_1,\...
user avatar
3 votes
5 answers
239 views

Show that $S=\{\mathbf x \in \mathbb R^n:\mathbf A \mathbf x=\mathbf b,\mathbf x \ge \mathbf 0\} \ne \emptyset$ has at least one extreme point

Show that the standard polyhedron defined by $S=\{\mathbf x \in \mathbb R^n:\mathbf A \mathbf x=\mathbf b,\mathbf x \ge \mathbf 0\} \ne \emptyset $ has at least one extreme point and the set of its ...
user avatar
  • 868
1 vote
2 answers
50 views

Does triangulation have to be finite for Sperner's Lemma to Apply?

I'm a little confused about a proof I read for Sperner's Lemma. The context was described as follows: Assume we have a $n$-dimensional simplex that is partitioned into smaller simplices that are ...
user avatar
0 votes
1 answer
24 views

Structure of the convex hull of $n$-dimensional 0/1 vectors with exactly $k$ 1s.

Let integers $1 \le k \le n$, let $I_{n,k}$ be the subset of binary vectors $v \in \{0,1\}^n$ such that $\sum_{i=1} v_i = k$, and let $\Delta_{n,k}$ be its convex hull. It is clear that $\Delta_{n,n} =...
user avatar
  • 8,289
1 vote
0 answers
19 views

embeddings of Khalimsky line into $\mathbb{R}$ matching with cubical complex digital geometry

The Khalimsky line can be embedded in $\mathbb{R}$ as follows 1: Let us identify with each even integer $m$ the closed, real interval $[m − 1/2,m + 1/2]$ and with each odd integer $n$ the open ...
user avatar
  • 1,356
2 votes
0 answers
31 views

For any planar graph $G$ with a cut vertex, we can always add a straight edge in some plane drawing of $G$.

Fáry's theorem states that any simple planar graph can be drawn without crossings so that its edges are straight line segments. Recently, when I was considering the drawing of plane graph, I ...
user avatar
  • 701
0 votes
0 answers
18 views

Neighborhoods of Doubly Covered Polygons

A.D Alexandrov in order to prove the existence of polyhedra with prescribed development, uses neighbourhoods in the manifold of closed and convex polyhedra. For the case of non degenerated polyhedra, ...
user avatar
  • 3,107
0 votes
0 answers
31 views

Splitting $d+1$ pairs in $\mathbb{R}^d$ such that the two convex hulls intersect.

I am struggling with the following problem. Given $d+1$ pairs of points $P_i=(x_i, y_i)\in \mathbb{R}^d\times \mathbb{R}^d$, $i=0,\ldots ,d$. Show that we can split the pairs $P_i$ into $u_i$ and $v_i$...
user avatar
0 votes
0 answers
21 views

Finding a point that always cuts a polygon into halfs of similar size

I've been trying to solve this problem: Let $P\subset\mathbb{R}^2$ be a closed polygon with area $A(P)$, not necessarily convex. Prove that there is a point $x\in\mathbb{R}^2$ such that every line ...
user avatar
  • 309
3 votes
1 answer
225 views

There exists matching of size at least $E(G)/\Delta(G)$ for bipartite graph.

To show: There exists a matching of size at least $|E(G)|/\Delta(G)$ for any bipartite graph $G$. ($\Delta(G)$ is the maximum degree) Approach. : If say $|E(G)|/\Delta(G)= k+\epsilon, 0\le\epsilon<...
user avatar
  • 33
2 votes
0 answers
18 views

Minor of an acyclic finite graph is acyclic as well

Let $G$ be a graph with no cycles. We want to either prove or disprove that any minor graph of $G$ is either acyclic or cyclic. My idea: If $G$ is cyclic, all connected components are trees. Choose ...
user avatar
0 votes
0 answers
50 views

The Fixed Points of an Elliptic Element in a Kleinian Group

Let $\Gamma$ be a Kleinian Group (a discrete subgroup of $PSL_2(\mathbb{C})$) acting on $\mathbb{D}=\{z \in \mathbb{C} : |z| \leq 1\}$. Let $\Lambda(\Gamma)$, $\Omega(\Gamma)$ be the Limit Set and the ...
user avatar
  • 2,214
-1 votes
1 answer
28 views

How to expand the following notation?

Can someone help me to expand the below equation for N=2 and N=3? $f_i=\sum \{e_i:j\leq i \leq k\}$ for some $1\leq j\leq k\leq N$. Here $e_i$ is the unit vector of coordinate i in an N-dimensional ...
user avatar
  • 1
0 votes
0 answers
25 views

How approach to demonstrate that the inequality $V(K)\le V(L)$ of compact set volumes of an Orlicz intersection body $K$ and a star body $L$ holds?

Even though a proof would be fantastic, please don't take this question as a request for a complete proof, but as a collector of ideas on how to deal with the stated inequality (visualizations, drafts ...
user avatar
1 vote
0 answers
18 views

Partioning rectangles into rectangles and valid sub-rectangle extension rules.

Given a rectangle $A$ composed of unit squares, we then fuse grid squares into sub-rectangles $B_i$ in a way that the $B_i$ partition $A$. Example: XXO YZO YWW ...
user avatar
  • 549
2 votes
1 answer
84 views

Zonotope: Image of the Diagonals of a Hypercube Under a Linear Map

Let $A \in \mathbb{R}^{m \times n}$ be a matrix where $m \leq n$, and let $H = [-1,1]^n$ be the unit hypercube. One can form the zonotope $\mathcal{Z}(A) = \{Ax : x \in H\} \subset \mathbb{R}^m$, ...
user avatar
1 vote
0 answers
24 views

Measures of Rotated Sets in $\mathbb{R}^n$

Let $S \subset \mathbb{R}^n$ be some "nice" bounded set whose diameter isn't "too small". We can define the measure $$ \nu (S) = \sum_{m \in \mathbb{Z}} \mathrm{Leb}\left( \lbrace \...
user avatar
0 votes
0 answers
15 views

Convex points with diagonals that are parallel to lines formed with convex points and an interior point

We have a set of $2k$ points on a convex hull and connect all of these points to one another with diagonals. Then we add a point $p$ in the interior of the convex hull so that this point is not placed ...
user avatar
0 votes
0 answers
34 views

Closest distance between a cube and the slices of a cylinder.

Suppose $B$ is an axis cube aligned in $\mathbb{R}^3$, i.e. the vertices are $0, e_1, e_2, e_3, e_1 + e_2, e_1 + e_3, e_2 + e_3, e_1 + e_2 + e_3$ where $e_1 = (1, 0, 0)$. Suppose $C$ is an infinite ...
user avatar
  • 915
0 votes
0 answers
128 views

Extreme points and convex hull

Definition 1: The convex hull of a subset $S$ of $\mathbb{R}^n$ is the smallest convex subset of $\mathbb{R}^n$ that contains $S$. I denote it by the symbol $\mbox{Conv}(S)$. If $S$ is a finite set, i....
user avatar
  • 179

1
2 3 4 5
14