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
1
vote
0answers
9 views

is every edge of a zonotope a generator?

Given a Zonotope $Z \subset \mathbb{R}^d$, with generators $G \in \mathbb{R}^{n\times d}$. Every facet is a $d-1$ polytope. And I'm wondering is it true that every edge of the facets is one generator ...
7
votes
1answer
83 views

Does this discrete curve have a name?

Generated using the following logic. Begin at a center starting point and draw two one-unit line segments from the center point in opposite directions. Draw two one-unit line segments that begin at ...
1
vote
0answers
25 views

Question about Minkowski-Weyl theorem and LP programming

Let $A$ a $m\times n$ real matrix , $b\in \mathbb{R}^m$ and $c\in \mathbb{R}^n$. I want to prove that if the linear program $P=\min \{c^\top x: Ax=b, x\ge 0\}$ is feasible and bounded, then it has an ...
4
votes
1answer
105 views

What is a plane figure covering all sets of diameter $1$?

Problem : (1) Show that there is a plane figure $F$ of least area which is capable of covering any plane figure of unit diameter. (2) Try to guess what is $F$. Proof of (1) : Define $\mathcal{H}$ to ...
1
vote
2answers
42 views

Having trouble understanding difference between polyhedron and polytope

Hi i´m reading a pdf about linear programming and i´m having trouble understanding the difference between a polyhedron and polytope between those two definitions A polyhedron P ⊆ $R^{n}$ is the set ...
1
vote
1answer
23 views

Application of Colorful Caratheodory for Directed Cycles

I'm working through Irme Barany's convexity lectures (http://wiki-math.univ-mlv.fr/gemecod/lib/exe/fetch.php/barany_lecture_2.pdf) and I am struggling to prove an exercise the author left to the ...
1
vote
1answer
23 views

Computationally simple way to find N26 direction

Assume we have an integral 3D grid $\mathbb{Z}^3$ and a set of line segments $V = \{((0, 0, 0), (x, y, z)): x, y, z \in \mathbb{Z} \land (x, y, z) \ne (0, 0, 0)\}$ from its origin to another grid ...
0
votes
1answer
29 views

Intersection lattice of a real braid arrangement.

In $\mathbb{R}^d$, the collection of hyperplanes $\mathcal{H}=\left\{x_{j}=x_{k}: 1 \leq j<k \leq d\right\}$ is called the $d$-dimensional real braid arrangement. I’m interested in the ...
1
vote
1answer
24 views

Distance from the center of a regular unit simplex to a vertex

I am working through Lectures in Discrete Geometry, and one of the questions goes as follows: Any point set of diameter $1$ in $\mathbb{R}^2$ can be enclosed in a disc of radius $1/\sqrt{3}$. Prove ...
1
vote
1answer
22 views

Covering compact convex $-C \subseteq \mathbb{R}^d$ with $x+dC$ for some $x \in \mathbb{R}^d$: counterexample?

From Matousek's Lectures in Discrete Geometry: Let $C$ be compact convex in $\mathbb{R}^d$. Prove that there is a suitable translation of $C$ blown up by a factor of $d$ which covers the reflection ...
0
votes
0answers
35 views

Is there a largest minimal non-guillotine pattern?

In this question, a pattern is an finite arrangement of pairwise-disjoint axes-parallel rectangles contained in some larger rectangle. A guillotine pattern (GP) is a pattern in which the rectangles ...
0
votes
1answer
33 views

VCdim of a range space that consists of all open disks of the R^d for some d

Please help me prove this question: For the range space $(\Bbb R^d, D_d)$ where $D_d$ consists all the open disks in $\Bbb R^d$, each disk in $D_d$ is in the form of: $D(p,r):=\{x\in\Bbb R^d | \Vert x-...
3
votes
1answer
168 views

To prove that the intersection of the given sets is not empty

Below is a question that I came across recently. Suppose $G = \text{conv}\{k_{1}, . . . ,k_{n}\}$ be a convex set in $R^{d}$. Then we have to prove that the intersection of $F_{i}=\{p :(-1/d)k_{i}+ p\...
0
votes
1answer
43 views

Points in space [closed]

Let $P =\left \{ A_{1}, A_{2} \cdots A_{n} : A \in \mathbb{R}^{3}\right \}$ (where $A_{0}=A_n, A_{1}=A_{n+1})$. By middling of a point $A_{i+1}$ we mean setting it's value to a rectangular projection ...
6
votes
1answer
193 views

Is this proof of Carathéodory's theorem valid?

I'm working through some discrete geometry and am trying to get a more rigorous grasp of convex geometry. In particular, I would like to try proving this theorem without the use of Radon's Lemma, ...
4
votes
2answers
150 views

Generalized Helly's theorem

Let $X_1,\ldots,X_n$ be convex sets in $\mathbb{R}^d$. Suppose the intersections of every $d + 1 − k$ of them contain an affine $k$-dimensional subspace. Prove that there exists an affine $k$-...
2
votes
0answers
52 views

If $Q$ is a polyhedron with lineality space $L$, then dim$(Q)$ = dim$(Q/L)$ + dim$(L)$, where $Q/L$ is $Q$ with $L$ “modded out”.

The definition of $Q/L$ from my course is a bit vague, but I assume it is as follows: if $Q = L + S$ (where “$+$” is the Minkowski sum), then $Q/L = S$. I realize that if we define $W$ to be the ...
5
votes
0answers
36 views

Which reflection groups contain central inversion?

Question: Which finite irreducible reflection groups $\Gamma\subseteq\mathrm O(\Bbb R^d)$ contain the central inversion $-\mathrm{Id}$, and how can this be spotted from the Coxeter diagram? The ...
1
vote
2answers
112 views

Cubes inscribed into a sphere

Suppose n ≥ 3 unit cubes are inscribed into a sphere, such that every three of them have a common vertex. Prove that all n cubes have a common vertex. Could anyone please help me the approach? Thanks ...
1
vote
1answer
34 views

Intersection of a pointed cone and a hyperplane is a polytope?

Let $C = \text{cone}(u_1,\dots,u_m)$ for some $u_1,\dots,u_m \in \mathbb{R}^d \setminus \{\textbf{0}\}$ be a finitely generated pointed cone. Let $H_0 := \{x \in \mathbb{R}^d: \langle a,x \rangle = 0\}...
6
votes
2answers
142 views

Tetrahedron circumradius in high dimensions [closed]

I guess this answer had already been answered a long time ago, but indeed I cannot find any reference. What is the circumradius of a $n$-dimensional regular hypertetrahedron? Does it approach the ...
1
vote
1answer
35 views

Do discrete geometric objects exist in the same space as non-discrete geometric object?

Do discrete geometric objects exist in the same space as non-discrete geometric object? I am wondering if the spaces are defined differently in discrete geometry. After reading a little about it, I am ...
2
votes
0answers
63 views

Triangle inscribed and circumscribed gap-filling radii sequences distinct?

Staring with an equilateral triangle $\Delta$, inscribe a circle, then in the gaps, inscribe other circles, ad infinitum. Similarly, inside the circumscribed circle but outside $\Delta$, continue to ...
0
votes
0answers
30 views

Intersection points convex hull and grid

I am trying to find the intersection points of the boundary of a convex hull of a finite set $S$ and a grid in multiple dimensions. How can I do this?
1
vote
0answers
46 views

Best algorithm for convex hull membership problem

Given a point $p \in \Bbb R^d$ and a finite set $S \subset \Bbb R^d$, I would like to determine if $p$ lies in the convex hull of $S$. A literature search informed me that there are a lot of different ...
0
votes
1answer
79 views

Prove that there is a unit circle intersecting all n lines

Suppose there are n lines in the plane such that for any three of them there is a unit circle intersecting each of them. Prove that there is a unit circle intersecting all n lines. How I have imagined ...
0
votes
1answer
58 views

Prove $|a − x| < |a − b|$

Prove that if $a, b, c$ are distinct points of $\mathbb R^d$ such that $∠abc < π/2$, then there is a $x$ on the open segment $(b, c)$ with $|a − x| < |a − b|$. I tried to take these points as ...
0
votes
1answer
26 views

Wouldn't an element of a set always spans a ray of the cone of that set?

For context, I'm reading the paper A linear optimization oracle for zonotrope computation. In algorithm 1, line 8, I don't understand the testing condition: For a discrete set $G \subset \mathbb{R}^n$....
2
votes
1answer
106 views

Ratio of obtuse triangles to acute triangles in the square.

I came across OEIS sequences A190020 and A190019, and I noticed that they seemed to grow at a similar rate. A190020: Number of obtuse triangles on a (n X n)-grid (or geoboard) A190019: Number of ...
1
vote
1answer
82 views

Supremum of a compact set

For a non-empty compact set C ⊂ R (or $R^2$) prove that there is the point x ∈ C such that y <lex x for any y ∈ C\ {x}. From the analysis, we know that supremum of any subset of R exits. And since ...
0
votes
0answers
21 views

Characterization of conjugate faces of mutually polar convex sets

This is exercise 6.6 in Arne Brondsted's "Introduction to Convex Polytopes": Let C and D be mutually polar compact convex sets. Let F be a proper exposed face of C and let $G = F^\triangle$...
1
vote
0answers
35 views

Bounding a curve in a pencil of circles

Let $B$ be a ball of radius $r$ whose diameter is defined by a line segment between the points $x,y$. Let $B_1, B_2$ be the two balls in the pencil of circles defined by the line segment $xy$ with ...
0
votes
0answers
20 views

How to find a projecting of a point into the intersection of semi-spaces? [duplicate]

I have a point $A\in\mathbb{R}^n$ and a set of $k$ constraints of the form $$a_i + \alpha a_j+ \geq \epsilon$$ for $\epsilon>0$ and $a_i$ the $i$ dimension of $A$. How can I find the projection of ...
0
votes
1answer
18 views

Rational fraction constructions with origami

I'm writing a paper on origami in maths and currently looking at approximating rational fractions using various methods: crossing diagonals, Fujimoto, Haga, Noma methods. Reading Origami and Geometric ...
1
vote
4answers
41 views

Number of Zonotope Edges Parallel to Generator

Suppose we have a zonotope $Z$ that is the Minkowski sum of line segments $U_1+\dots +U_n$. All the edges of $Z$ are parallel to some $U_i$. Is it also true that the number of edges parallel to $U_i$ ...
1
vote
1answer
113 views

An extension of Helly's theorem

Let $A ⊂ \Bbb R^2$ be a fixed convex set and let $X_1, \cdots , X_n ⊂ \Bbb R^2$ be any convex sets such that every three of them intersect a translation of $A$. Then there exists a translation of $A$ ...
1
vote
0answers
42 views

Show that there is a constant C > 0 so that for any set A = {a1, . . . , an} of n > 0 distinct real numbers

For any two sets A, B of real numbers denote A + B := {a + b | a ∈ A, b ∈ B} and A × B := {a · b | a ∈ A, b ∈ B}. Show that there is a constant C > 0 so that for any set A = {a1, . . . , an} of n &...
0
votes
0answers
17 views

Can a regular triangular grid graph expressed as a transformation of a regular square grid graph?

I was wondering how would I describe a regular triangular grid graph as a transformation of a regular square grid graph? This is the way I thought about it: if I have a grid graph consisting of ...
0
votes
0answers
46 views

Problem on halfplanes

Let F be a finite collection of halfplanes covering the plane. Prove that there are three halfplanes of F covering the plane. So I understand that half-planes are formed when a line divides the plane ...
0
votes
1answer
82 views

Number of integer points inside an equilateral triangle with side length $n\in\mathbb{N}$

Does there exist any $n\in\mathbb{N}$ such that there exist at least one point inside of(not on the border) an equilateral triangle with side length $n$ ,which its distances to the vertices be ...
0
votes
1answer
70 views

Helly's theorem.

Let F be a finite family of segments in R such that among any n of them there are two intersecting. Prove that it is possible to divide F into n−1 families such that any two segments in one family are ...
0
votes
0answers
14 views

No set of 4 points can be shattered by a line and Radons theorem

I am reading the wikipedia article about Vapnik–Chervonenkis dimension and do not understand the following statement: No set of 4 points can be shattered: by Radon's theorem, any four points can be ...
1
vote
0answers
13 views

How can Radon's lemma be useful?

Radon's lemma states: Let A be a set of $d$+2 points in $R^{d}$. Then there exist two disjoint subsets $A1$, $A2$ $\subset$ $A$ such that $conv(A1)$ $\cap$ $conv(A2)$ = $\emptyset$ I understand that ...
0
votes
0answers
10 views

Number of faces and edges in Delaunay diagram

Let us have a set of $n$ points, of which $m$ points are in the convex hull of the $n$ points, $k$ points are cocircular. Assuming that the other points $(n-k-m)$ are neither cocircular (any four of ...
1
vote
1answer
73 views

Book recommendation on Discrete Geometry

I have started studying discrete geometry. And I need some good suggestion on discrete geometry books. I am looking for something rigorous with a lot of solved example (if possible). Some books that I ...
2
votes
1answer
109 views

Upper bound for the total curvature of a shortest path in the boundary of a convex polyhedron in $\mathbb{R}^3$.

Consider finitely many points in $\mathbb{R}^3$. The boundary of the convex hull is $\Sigma$. When $f_i$ is a face and $u_i$ is unit outnormal to $f_i$, then assume that $$(-u_1)\cdot u_i >\eta>...
1
vote
0answers
76 views

Problem on Helly's theorem

Let F be a finite family of segments in R such that among any n of them there are two mutually disjoint. We have to prove that it is possible to divide F into n− 1 family such that any two segments in ...
1
vote
0answers
54 views

Question Regarding Complete Normal Fans and Duality

I have a question regarding the definition of a normal fan. The definition is thus: "Given a non-empty polytope $P \subset \mathbb{R ^d}$, the normal fan $N(P)$ of $P$ is the fan consisting of, ...
0
votes
0answers
12 views

How to visualize rotation of valid inequalities for facets of polyhedra?

I’m looking at the following analysis. Let $P=\{x: A x \leq b\}$ for $A, b$ integral. Let $F$ be a facet of $P$. So $F=\left\{x: A^{0} x \leq b^{0}, A^{1} x = b^{1}\right\}$ for some partitioning $A^{...
4
votes
1answer
70 views

Is a pyramid uniquely determined by its edge-lengths?

I am looking for a nice/short proof of the following: The shape of a pyramid with a convex polygonal base is already uniquely determined by knowing the length of all its edges. By "knowing the ...

1
2 3 4 5
12