Skip to main content

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
0 answers
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 ...
Andrew Marks's user avatar
2 votes
1 answer
27 views

Dialation of a convex set covers its mirror

Problem: Let $C\subset \mathbb{R}^d$ be a compact convex set. Prove that the mirror image of $C$ can be covered by a suitable translate of $C$ blown up by the factor of $d$; that is, there is an $x \...
agent_cracker103's user avatar
0 votes
1 answer
121 views

How to identify the basis generated by figures?

I got this slide from the class lecture. My questions are: Q1. Why "there are enough vectors" are required for the linear span of vectors to satisfy 1st condition of basis? And why "...
David's user avatar
  • 500
0 votes
1 answer
38 views

Tessellation of figures [closed]

I'm currently pondering the following problem: "In how many equal parts can I divide a figure?" The minimum unit is the square, so diagonal lines cannot be drawn. I have solved it for these ...
Shinj's user avatar
  • 1
0 votes
0 answers
17 views

How to morph enclosed mesh according to the enclosing mesh?

I am quite new to meshing and mesh manipulation. I am working on a problem consiting of meshes $A$, $B$, and $C$. The mesh $C$ completely encloses the meshes $A$ and $B$ as shown in the attached ...
Prakhar's user avatar
  • 117
-3 votes
1 answer
176 views

Finding a Point with Null Real Derivative on a Cubic Path [closed]

Let's examine a cubic complex function $F(z) = z^3 + e_1z^2 + e_2z + e_3$ with $z$ in the complex numbers. Suppose this function zeros out at two points, $m$ and $n$, which lie inside the boundary of ...
Snowball's user avatar
  • 992
2 votes
1 answer
52 views

What are the possible surfaces that one can construct from a finite set ot triangles?

I am looking for references in discrete differential geometry for a concept I've been interested in. It is very common to approximate smooth surfaces using discrete triangulations. I am interested in ...
Einav Brin's user avatar
7 votes
1 answer
90 views

How close do distinct distances to $0$ determined by a square integer lattice in $\mathbb{R}^2$ get?

Recently on MSE's chat, user "Simd" raised the following problem (I have rephrased and introduced some notation): For $n \geq 1$ let $S_n \subseteq \mathbb{R}^2$ denote the Cartesian ...
leslie townes's user avatar
0 votes
0 answers
38 views

Number of hexagonal lattice points inside a circle

Consider a regular hexagonal lattice, like so Given a circle centred at a vertex in this lattice, with radius $r\in\mathbb{R}^+$, is the number of lattice points inside this circle known? Note: The ...
sam wolfe's user avatar
  • 3,417
0 votes
0 answers
20 views

largest ratio between 2 points' Euclidean distance and edge distance over all pairs of points on a planar polygon's edges

A geometry problem I worked on in a REU program from years ago just came to my mind. Let's define a constant called "chord-arc constant" for any planar polygon as the largest ratio between 2 ...
hu362's user avatar
  • 1
0 votes
1 answer
32 views

Subrings generated by lattice groups in algebras of continous functions

This is probably false but can't find a good counterexample. Let $X$ be a compact space and consider the algebra $C(X)$ of all scalar-valued continuous functions on $X$ endowed with the supremum norm. ...
Tomasz Kania's user avatar
  • 16.4k
0 votes
0 answers
18 views

Every subset of vertex set defines a face of a polytope then it is a simplex

As the title suggests, I am trying to prove: Prove that if any subset of the vertex set of a polytope defines a face, then the polytope is a simplex. For polytope $P$ with $n$ vertices $\{v_1,...,...
Anon12's user avatar
  • 31
0 votes
0 answers
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 ...
jcdornano's user avatar
  • 351
0 votes
0 answers
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$ := ...
wiop's user avatar
  • 1
0 votes
0 answers
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 ...
user1072285's user avatar
0 votes
0 answers
30 views

Union of convex polytopes with non-linear upper bounds is till a convex polytope?

This is a follow-up of this. Suppose I have a union set, $\bigcup\limits_{\{\mathbf{q}_k\}_{k=1}^n:\mathbf{q}_k \in\mathbf{P},\forall k\in\{1,2,...,n\}}A(\{\mathbf{q}_k\}_{k=1}^{n})$, where $A(\{\...
jerry's user avatar
  • 135
3 votes
2 answers
192 views

Infinite union of convex polytopes is till a polytope? (Union among probability simplex)

Suppose I have a union set, $\bigcup\limits_{\mathbf{q} \in\mathbf{P}}A(\mathbf{q})$, where $A(\mathbf{q})$ is a $n$-dimensional hypercube defined by $$A(\mathbf{q}) = \left\{ \mathbf{x}\in\mathbb{R}^...
jerry's user avatar
  • 135
0 votes
1 answer
74 views

Intersection of convex hulls of two disjoint sets

Suppose that I have a finite set in $\mathbb R^n$, $A:=\{x_1,\ldots,x_n\}$. I want a condition on this set such that $co(S) \cap co(T) = \emptyset$ for any $S,T \subset A$ with $S \cap T = \emptyset$, ...
avk255's user avatar
  • 431
1 vote
0 answers
42 views

Why this $2$-dimensional polytope has two different half-space representations? What is the geometrical intuition behind this?

Let a $2$-dimensional polytope given by the vertices $P_1=(0, -1)$, $P_2=(-1, 0)$, $P_3=(-1, 2)$, $P_4=(1, 0)$, $P_5=(1, -1)$: When I use different libraries to obtain the half-space representation, ...
Eldar Sultanow's user avatar
4 votes
1 answer
173 views

How to derive A001187 formula combinatorically

I’ve learned recently that the formula for A001187 is defined recursively. The formula is: $$n2^{\binom n2}=\sum_{k=0}^{n} \binom{n}{k}kd_k2^{\binom{n-k}{2}}$$ Where $d_k$ is the number of connected ...
badatmathman's user avatar
2 votes
1 answer
80 views

Line segments in compact convex sets

I'm struggling with a problem of Lecture on discrete geometry by Matusek. Given $C\subset\mathbb{R}^{d}$ a compact and convex set and $p$ an interior point of $C$, it asks to prove the existence of a ...
Yeipi's user avatar
  • 513
0 votes
0 answers
26 views

Proving that if $n$ hemispheres cover a sphere, it is possible to choose 4 hemisphere that also cover the sphere.

The question is taken from Cool Induction Problems. Quoting: (**) A sphere is covered with some number of “caps” which are hemispheres. Prove that it is possible to choose four hemispheres, and ...
by24's user avatar
  • 998
3 votes
1 answer
83 views

Largest number of corner pieces in an $m \times n$ grid?

The other day the following combinatorics problem popped into my head: Given an $m \times n$ grid, how many corner pieces can fit in it without overlapping? A corner piece is defined as such: ...
David's user avatar
  • 31
1 vote
1 answer
42 views

Finding the feasible region of a system of convex / monotone inequalities?

Let $x$ and $y$ be variables in $\mathbb{R}^{+}$, and assume I have a system of inequalities, e.g.: $$ \begin{align} x \geq 1 \tag{1}\\ x \leq 5 \tag{2}\\ y \geq 1 \tag{3}\\ \log x + \log y \leq \log ...
J.Galt's user avatar
  • 961
1 vote
1 answer
82 views

$\sum_{i=1}^{\infty} 2^{-{i^{i}}}$ is not algebraic

As title suggests, I want to prove that $\sum_{i=1}^{\infty} 2^{-{i^{i}}}$ is not an algebraic number. From the book I found this claim (Lectures on Discrete Geometry) it looks an immediate ...
Yeipi's user avatar
  • 513
1 vote
0 answers
67 views

Why is the discrete $1$-form associated with a homology generator not exact?

In these course notes, the author constructs a $1$-form from a given homology generator in the following way: Then, he claims that the integral of $\omega$ over the generator is nonzero, and hints at ...
Francisco José Letterio's user avatar
0 votes
0 answers
33 views

Why is the discrete exponential map not injective once a path reaches a saddle vertex?

I'm reading the following survey on algorithms for computing geodesic paths on discretized surfaces: http://www.cs.cmu.edu/~kmcrane/Projects/GeodesicSurvey/GeodesicSurvey.pdf According to the authors, ...
Francisco José Letterio's user avatar
0 votes
1 answer
33 views

Uniqueness of generator set for zonotope

This might be a very simple question, but the answer is not entirely obvious to me and I've been unable to find it stated anywhere. Consider two sets of generators (vectors), which are reduced in the ...
Scott's user avatar
  • 65
0 votes
0 answers
63 views

Automorphism group of a Polytope

I have been given the following task: Let $P \subseteq \mathbb{R}^d$, a polytope, such that $P = \text{conv}(K)$ for $K \subseteq S^{d-1}$ finite, where $S^{d-1}$ denotes the Euclidean unit sphere in $...
Harry's user avatar
  • 23
1 vote
1 answer
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?...
pritam's user avatar
  • 10.2k
1 vote
0 answers
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 ...
Zihan Zhao's user avatar
2 votes
1 answer
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 ...
hello_123's user avatar
  • 435
7 votes
1 answer
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 ...
maomao's user avatar
  • 1,219
3 votes
1 answer
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 ...
Fabius Wiesner's user avatar
0 votes
0 answers
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 &...
Drew Armstrong's user avatar
0 votes
1 answer
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: ...
Gragarian's user avatar
1 vote
1 answer
145 views

Problem on geometric arrangement of lines in space

Consider a set of $n$ lines in $\mathbb{R}^3$ all concurrent in a point (let's call it center). Is it always possible to place a finite number of isometric copies of this set of lines in $\mathbb{R}^...
Lucio Tanzini's user avatar
6 votes
3 answers
273 views

What is the distribution of distances between two random points in RGB space?

Suppose we pick pairs of triples from $\{ 0, 1, 2, \dots, 255\}^3$ with a uniform distribution and would like to find a closed form for the distribution of the Euclidean distances $$ d((x_1, x_2, x_3),...
Teg Louis's user avatar
0 votes
0 answers
43 views

Convex hull of a set of $2^{n-2}$ points without a convex subset of $n$ points

I was recently looking at the happy ending problem, and on the linked Wikipedia page, there is the following conjecture (the Erdos-Szekeres conjecture), which states the following: The smallest ...
Varun Vejalla's user avatar
1 vote
1 answer
223 views

Intuition on the cotangent weights in the discrete Laplacian

The discrete Laplacian matrix: $L_{ij} = $ $ \begin{cases} w_{ij} = \frac{1}{2} \left(cot\; \alpha_{ij} + cot \;\beta_{ij}\right) \text{if $j$ is adjacent to $i$}\\ -\sum_{j \in \mathcal{N(i)}} w_{...
Cedric Martens's user avatar
0 votes
0 answers
45 views

Discreteness of $D^{-1}D$ given that $D$ is uniformly discrete

Let $G$ be a topological group with unit element $e$. We say that $D\subseteq G$ is discrete if for all $x\in D$ there is a unit-neighborhood $U\subseteq G$ such that $x^{-1}D\cap U=\{e\}$. We say ...
mathemagician99's user avatar
0 votes
0 answers
22 views

Finding safe points in polygons

Let $P$ be an axes-parallel polygon. A point $(x,y)\in P$ is called safe if for any pair $d_x\in[0,1],d_y\in[0,1]$, either $(x+d_x,y+d_y)$ or $(x-d_x, y-d_y)$ or both are in $P$. Figuratively, suppose ...
Erel Segal-Halevi's user avatar
1 vote
0 answers
60 views

The number of faces of a pointed convex polyhedral cone

Let C be an n-dimensional pointed convex polyhedral cone with a uniqe frame {a1.a2.......,ar}, where ais are extrem half-lines. Is there a formula for the number of r-faces in C? Let me state the ...
Masahiro Fujimoto's user avatar
2 votes
0 answers
115 views

How to find the convex hull of the set $\left\{ {\bf x} \in \{0, 1 \}^n \mid {\bf 1}_n^\top {\bf x} = k \right\}$?

Given integers $k < n$, let $$ \mathcal{V} := \left\{ {\bf x} \in \{0, 1 \}^n \mid {\bf 1}_n^\top {\bf x} = k \right\} $$ Is it true that its convex hull is $\mathcal{S} := \left\{ {\bf x} \in[0,1]^...
Zang San's user avatar
-2 votes
2 answers
93 views

Why is the convex combination of $3$ points in $\Bbb R^2$ a triangle and not a V-like shape? [closed]

I am new to convexity. I do find it really confusing why the convex combination of $3$ vectors (points) is a triangle and not a V-like shape. With $2$ vectors, it is a segment then why is the case of $...
Yugant Shewale's user avatar
3 votes
0 answers
68 views

Characterizing the incidence graphs that correspond to a system of points and lines in the plane

The incidence graph of a system of points and lines in $\mathbb{R}^2$ is the bipartite graph with partite sets $P, L$, where $P$ corresponds to the points, $L$ corresponds to the lines, and we add the ...
Gary Hoppenworth's user avatar
0 votes
0 answers
19 views

The connectivity of reflexive polytopes from just their vertices?

I'm working with the Kreuzer-Skarke database of 4-dimensional reflexive polyhedra. It lists almost half a billion polytopes, each represented by its vertex list and a few properties (Hodge numbers and ...
Eddie V's user avatar
2 votes
0 answers
58 views

How to find a set of linear inequalities from the vertices of a $d$-dimensional convex polytope?

Let $S = \{x_0, \dots, x_n\} \subseteq (\mathbb{R}^+)^{d}$ be the set of vertices of a convex $d$-dimensional convex polytope ($d \geq 2$). I am interested in finding a set of linear inequalities such ...
Nicolec's user avatar
  • 21
1 vote
1 answer
64 views

Can we split a triangle into $4$ components of equal area like this?

If I am given a triangle of any shape, and I label its edges as $e_1,e_2,e_3$, can I find two lines $L_1$ and $L_2$ that fulfill the following conditions: $L_1$ is parallel with $e_1$, $L_2$ is ...
eng_tun_0103's user avatar
1 vote
0 answers
32 views

Jacobi field on polygonal mesh

I want to compute Jacobi fields on polygonal meshes. The problem is that on each face, two geodesics starting parallel will remain parallel until they pass a vertex from different sides. Passing a ...
Einav Brin's user avatar

1
2 3 4 5
15