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
0answers
7 views

Getting an equivalent description of reflexive polytopes

In the proof of Theorem 4.6 from Computing the Continuous Discretely by Beck and Robins, the authors want to prove the equivalence of some descriptions of relfexive polytopes: $\mathcal{P}=\{\mathbf{x}...
0
votes
0answers
28 views

Example of non-contractible acyclic finite simplical complex

From the article "f-vectors of acyclic complexes" (Discrete Math. 1985) by Gil Kalai, we know that the relation between f-vectors of an acyclic simplicial complex. In other words, one can construct ...
2
votes
0answers
27 views

On a question of contractible graphs

A family $\mathcal{F}$ of graphs $G_1, G_2, \cdots, G_n ,\cdots$ is called contractible if (1) The trivial graph, $\ast \in \mathcal{F}.$ (2) Any graph of $\mathcal{F}$ can be obtained from the ...
0
votes
2answers
26 views

Inclusion of polytopes

Let $C_{1}$ and $C_{2}$ be polytopes in $\mathbb{R}^{n}$ such that $C_{1}=conv\left( V\right) $ with $V$ being a set of vertices. If $V\subseteq C_{2}$, my question is $C_{1}\subseteq C_{2}$?
1
vote
1answer
40 views

Probability of crossing $n\times n$ grid with random diagonals; and bond percolation critical threshold $p_c$

You can always cross an $n\times n$ grid with random diagonals, from one side of the grid to the opposite side of the grid. So the probability of this crossing is $1$. Here random diagonals means you ...
0
votes
1answer
17 views

Criteria for checking if points are the vertices of a hypercube

I asked a question over at Code Golf Stack Exchange which essentially asked folks to write a program to determine if a collection of $2^n$ points in $\mathbb{Z}^m$ is the vertex set of some $n$-...
2
votes
2answers
68 views

Points in a triangular lattice at the same distance from the origin and “breaking of symmetry”

Introduction I was trying to simulate what would happen to a certain physical system taking place in a triangular lattice (the physical details are not relevant to the discussion), when I came across ...
0
votes
0answers
12 views

What are some interesting variations of the problem of the art gallery?

The art gallery problem or museum problem is a well-studied visibility problem in computational geometry. It originates from a real-world problem of guarding an art gallery with the minimum number of ...
0
votes
0answers
22 views

How do I prove that the intersection of two convex polyhedra is a convex polyhedron?

I'm studying about convex geometry, and that is my problem. for more details: A polyhedron is a convex hull of finite points. P is a polyhedron then P := conv{x1,..,xn}
27
votes
1answer
619 views

Number of ways to stack LEGO bricks

One of the most surprising combinatorial formulas I know of counts the number of LEGO towers built from $n$ "$1 \times 2$" blocks subject to four rules: The bricks lie in a single plane. Each brick ...
1
vote
0answers
24 views

Proof of double counting formula

Let $v_k$ be the number of vertices of degree $k$, V and E the set of vertices and edges respectively. Then $|V| = \sum_k v_k$. I have to show the double counting formula for a closed surface: $$ \...
2
votes
2answers
67 views

Connected path of diagonals across an $n\times n$ grid, and Lemma of Sperner

Given an $n\times n$ grid where we draw at random one diagonal in each of the 1×1 unit squares. Then we can always find a connected path using these small diagonals that goes from one side of the grid ...
3
votes
2answers
61 views

On an $n\times n$ grid, with white and black tiles: is there always a connected path across the grid?

Assume you have an $n\times n$ grid, and a set W of white and a set B of black tiles that are placed randomly on this grid. I think that at least one of the sets W, B must include a connected path ...
1
vote
0answers
28 views

Problem about Tverberg number: Let $d,r_1,r_2$ natural numbers then we have $T(d,r_1r_2)$ $<=T(d,r_1)T(d,r_2)$

Im studying the book "Lectures on Discrete Geometry" of Jiri Matousek. The chapter 8.3 is about the Theorem of Tverberg which says: Let d and r natural numbers. For any set $A\subset R^d$ of at least ...
1
vote
0answers
24 views

Properties of set of points

Here is tinder fungus: and it's pores: I was wondering what can be said about this pattern. Using Wolfram Mathematica we can get the following results. Delaunay triangulation: Voronoi diagram: ...
0
votes
1answer
27 views

Construct a discrete subset such that every point of $\partial D$ is a limit point of discrete subset

$D$ is a domain in $\Bbb C$, please construct a discrete subset $E$ of $D$ such that every point of $\partial D\subset \Bbb C$ is a limit point of $E$ $D$ is a unbound domain in $\Bbb C$, please ...
1
vote
1answer
37 views

Expected number of cuts to partition the interval $[0, n]$ into segments of unit length or less

This is the one dimensional case of a more general problem I posted, linked here. Given an interval of length $n$, define a cut as a point somewhere in the interval. In expectation, how many ...
6
votes
3answers
104 views

If $u_i\cdot u_j<0$ for all $u_0,…,u_n\in\Bbb R^n$, then the $u_i$ cannot lie in the same halfspace?

Given a set of $n+1$ vectors $u_0,...,u_n\in\Bbb R^n$ with pair-wise negative inner product, that is, $u_i\cdot u_j<0$ for $i\not=j$. Question: what is a quick and clean way to see that the $u_i$...
1
vote
0answers
42 views

How to arrange points on a plane to minimize the maximum distance between any two of them?

How to arrange n points on a plane such that the distance between any two points is at least $1$ and the maximum of the distances between two points is minimized? It sounds like a world-famous ...
3
votes
1answer
87 views

Choosing representatives with spatial separation

There are $n$ sets of $k$ points in the 2-dimensional plane. Following the recent social distancing instructions, the distance between each two points in the same set is at least 2. We would like to ...
0
votes
1answer
48 views

How can the equation $Ax=b$ represent a polyhedron?

I can understand how inequalities can be used to define a polyhedron, for example, each plane in a 3d setting would be one face and putting all the planes together we would get a closed body with the ...
0
votes
1answer
9 views

dimension of proper face of a polyhedron

Let $\mathcal{P} = \mathcal{P}(A,b) = \{x \in \mathbb{R}^{n} \mid Ax \leq b\}$ be a polyhedron with $A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^{m}$. Let $\mathcal{F} \subset \mathcal{P}$ be a ...
20
votes
2answers
1k views

Convex polygons that do not tile the plane individually, but together they do

I am looking for two convex polygons $P,Q \subset \Bbb R^2$ such that $P$ does not tile the plane, $Q$ does not tile the plane, but if we allowed to use $P,Q$ together, then we can tile the plane. ...
1
vote
0answers
12 views

How can I define a Goldberg polyhedral with nearly-regular hexagons, given a hexagon width and sphere circumference?

I'm trying to create a "hexagonal grid" that covers the planet earth with nearly regular hexagons. I understand that, by including 12 pentagons, the remainder of a sphere can be covered by pseudo-...
1
vote
0answers
35 views

o($n \log n$) algorithm for a noncrossing matching in plane

I am thinking about the algorithm for the following well-known mathematical problem. $n$ red points and $n$ blue points in the plane in general position are given. Find the matching $\{r_1, b_1\}, \...
0
votes
2answers
54 views

Algorithm for checking if a polyhedron is bounded. [closed]

Given a polyhedron in the form $Ax \leq b$, I need to know a way to determine if the polyhedron is bounded. I need an algorithm for which given a matrix $A$ and a vector $b$ as input, it should ...
0
votes
1answer
21 views

Dual set of the unit ball with radius r

Define the unit ball centered at the origin with radius r as $B(0,r)=\{x \in \mathbb{R}^d:||x||\leq 1\}$ Define the dual set of a set X as $ X^*=\{y \in \mathbb{R}^d: x^Ty \leq 1,\; \forall x \in X \}...
3
votes
1answer
78 views

On a certain discrepancy measure between probability distributions on the symmetric group of permutation $\mathfrak S_n$

Let $\mathfrak S_n$ be the symmetric group of permutations on $n$ objects and let $P$ and $Q$ be a probability distributions on $\mathfrak S_n$ (i.e $P$ and $Q$ are points on the $n!$-simplex). For $1 ...
0
votes
0answers
16 views

Discrete case - Gaussian curvature preservation

Under isometric deformation of discrete space, will the Gaussian curvature at every point be preserved individually or the total curvature would be preserved? Like if we have the point to point ...
4
votes
2answers
45 views

Density of full $k$-dimensional affine subspaces of $\mathbb{F}_{p}^{n}$.

Let $p$ be an odd prime and let $\mathbb{F}_{p}^{n}$ be the $n$-dimensional vector space over the field of $p$ elements. Consider a subset $A\subseteq \mathbb{F}_{p}^{n}$ with density at least $\...
0
votes
1answer
41 views

Any $d+1$ affinely independent points can be shattered by the half spaces in $\mathbb R^d$

I am studying the VC-dimension of half spaces. There is a theorem in my book stating that, if $\mathcal H$ is the family of half spaces in $\mathbb R^d$, then VC-$dim(\mathcal H)=d+1.$ And the proof ...
-1
votes
2answers
21 views

Set of all polynomials (with nonneg coeffs, const. term 1) is convex

The question is as follows: Prove that the set of all polynomials in $x$ with nonnegative coefficients and constant term 1 is convex. Is this just meaning that it follows the form $\lambda x + (1- \...
1
vote
2answers
36 views

Convex Geometry: Affine & Linear Dependency's Relationship

The question is as follows: Let $x_1, x_2, ..., x_n \in \mathbb{R}^d,$ and for every $i = 1, 2, . . . , n,$ let $y_i = (x_i , 1) \in \mathbb{R}^{d+1}$. Show that $x_1, x_2, ... , x_n$ are affinely ...
1
vote
2answers
58 views

Is there a primitive Heronian triangle with two integer heights?

I found no primitive Heronian triangle with two integer heights in Heronian triangles with side length no more than 100. So I want to know the solution of the following problem. Is there a primitive ...
3
votes
1answer
91 views

Bound for the sum of vectors in $\mathbb{R}^n$

I have the following problem (it seems to be very famous, but I couldn't find reference) Problem. Given $k$ vectors $v_1,v_2,\ldots,v_k\in\mathbb{R}^n$ such that for each $i$ the inequality $|v_i|\...
3
votes
1answer
45 views

Counting deltahedra with $2n$ faces

A deltahedron is, according to Wikipedia, a polyhedron whose faces are all equilateral triangles. There is only one deltahedron with four faces: the tetrahedron. Likewise, there is only one ...
1
vote
0answers
32 views

Cups and caps inequality: $f(s,t) \leq {s+t-2 \choose {s-2}}+1$

A sequence of consecutive line segments in $\mathbb{R}^2$ is called a Cap if their slopes are monotonically decreasing, and a Cup if their slopes are monotonically increasing. Let $f(s,t)$ denote the ...
1
vote
1answer
51 views

Direct sum of two polyhedra is a polyhedron

This is HW, and I have read Sum of two polyhedra is a polyhedron but I don't understand the solution posted (is $M$ a polyhedron? Why do we take the projection? Why is the projection of $M$ a ...
0
votes
1answer
24 views

Set inclusion between convex polytopes with $\mathcal{H}$-representation

Let $\mathcal{P}_1$ and $\mathcal{P}_2$ be two convex polytopes with $\mathcal{H}$-representation, i.e., \begin{align} \mathcal{P}_1 &= \{x \in \mathbb{R}^n\colon A_1x \leq b_1\},\\ \mathcal{P}_2 ...
-1
votes
1answer
19 views

Volume of convex polytope with $\mathcal{H}$-representation

Consider the convex polytope $\mathcal{P} \subset \mathbb{R}^n$ with $\mathcal{H}$-representation $$\mathcal{P} = \{x \in \mathbb{R}^n\colon Ax \leq b\},$$ where $A \in \mathbb{R}^{m\times n}$ and $...
3
votes
1answer
58 views

What is the dual cone of a convex polyhedron?

A convex polyhedron is defined as $P=\{x \in \mathbb{R}^n \mid Ax \geq b\}$. On the other hand, the dual cone of any set $S$ is defined as $S^{*}=\{ y \in \mathbb{R}^n \mid x^{\top}y \geq 0 \,\,\,\,\,\...
2
votes
1answer
42 views

What is the function of the equation set in the definition of a polyhedron?

In the Chapter 2 of Convex Optimization by Boyd and Vandenberghe. The definition of a polyhedron is as follows: A polyhedron is defined as the solution set of a finite number of linear equalities ...
0
votes
1answer
40 views

Number of 1d- and 2d-cells in barycentric subdivision

I'm supposed to compute the number of 1- and 2-dimensional faces of a $k$-simplex after one step of barycentric subdivision. I already figured out that a triangle splits into $6=3!$ triangles as can ...
2
votes
1answer
55 views

On finding a finite set of generators for a certain semigroup

Let $A$ be a finite subset of $\mathbb Z^2$. Let $\mathbb ZA$ be the subgroup of $\mathbb Z^2$ generated by $A$. Let $\mathbb R_{+}, \mathbb Q_{+}$ denote the set of non-negative real and rational ...
1
vote
0answers
23 views

Configuration of $n$ lines on the plane: reference

Suppose that given $n$ lines on the plane with no three concurrent and no two parallel. Then, there are a lot of well-known results about that configuration (number of regions formed by these lines, ...
1
vote
0answers
35 views

Is there any efficient algorithm to compute the intersection of two polytopes?

Let $P_1$ and $P_2$ being two polytopes defined by their vertices. I there any efficient way to compute $P_3 = P_1 \cap P_2$? It seems the intersection of the polytopes can be represented as the ...
0
votes
0answers
53 views

Formula for number of squares fitting into a right angle triangle

Is there a known formula for the number of squares of a certain size that would fit into a right angled triangle?
3
votes
2answers
80 views

Prove that a polyhedron in the $\mathcal{H}$-representation is bounded

Given a polyhedron $P$ specified by a set of linear constraints $P=\{x \in \mathbb{R}^n \mid Ax \le b \}$, what are the conditions on the matrix $A$ such that $P$ is bounded? I have the following ...
2
votes
1answer
88 views

When does a given system of linear inequalities form a bounded convex polytope?

We know that a Closed Convex Polytope may be regarded as the set of solutions to the system of linear inequalities: $$\begin{array}{ccc}{a_{11} x_{1} +a_{12} x_{2}+\cdots+a_{1 n} x_{n}}\leq b_{1} \\ {...
16
votes
3answers
245 views

How close are the closests cells of the same color in a periodically colored grid?

In a square grid, if we have a coloring of the form $c(x, y) = (x + ny) \bmod m$, what is the minimum (positive!) taxicab distance (i.e. sum of absolute value fo coordinates) between different cells ...

1
2 3 4 5
10