Questions tagged [discrete-geometry]
Discrete geometry includes the study of covering, illumination, packing, convex bodies, convex polytopes, and other metric geometry.
692
questions
0
votes
0
answers
20
views
Algorithm for triangulation of 2D "point cloud" [closed]
EDIT:
I need an algorithm which as an input takes 2D array of colors - white and black, and as an output array of 2D vectors which will be coordinates to the input array. Those vectors should form ...
- 1
0
votes
0
answers
10
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 ...
1
vote
0
answers
27
views
What is a good way of defining an $A_k$ singularity for a discrete function?
Definition: Let $f$ be a smooth function defined on a neighborhood of some $t_0 \in \mathbb{R}$. Then for each integer $k \geq 0$, we say $f$ has an $A_k$ singularity at $t_0$ iff $\forall p, \, 1 \...
1
vote
0
answers
26
views
Extreme rays, recession cone of polyhedron
We have a polyhedron $P\subset R^2$ defined by:
$P:=\{ x\in R^2$
$4x_1-2x_2 \leq -8$
$−x_2≤2$
$-2x_1-x_2≤-4$
$−2x_1+x_2≤0$
Let X={(2,0)} Y{(1,2)}
a) Find the dimension of the smallest face $F\subset P$...
- 101
0
votes
0
answers
21
views
Intuition on $P_3$ and $P_4$-free graphs
I am struggling to understand the structure of $P_3$ and $P_4$ graphs. Could someone provide me a few examples of graphs from each of these two classes?
- 63
0
votes
0
answers
37
views
Why adding row of 1s makes entries of kernel add up to 0?
This is basically Gale transform.
If we have a set of $n$ vectors that affinely spans $R^d$, make a matrix out of them (vectors = columns of a matrix) and then add another row of 1s. Basically, the ...
0
votes
0
answers
20
views
Normal fan definition
I am struggling with the definitions of a normal fan. Here is how it is defined in Ziegler's book:
My question is how do I take the cone of a linear function which is maximal on a fixed face of P? For ...
3
votes
1
answer
122
views
Polyhedra has more corners than facets [closed]
Let $P$ be a polyhedron. Is it true that $P$ has always more/as many corners than facets? I haven't found a counterexample in $\mathbb R^2$ and $\mathbb R^3$ and intuitively I think the statement is ...
- 338
2
votes
0
answers
60
views
Show $2$-degenerate graphs are subgraphs of $2$-degenerate plane bipartite graphs
I am trying to prove or find a counterexample for the following claim: any planar $2$-degenerate graph is a subgraph of a $2$-degenerate plane bipartite graph (a planar graph whose faces are all $4$-...
- 63
0
votes
0
answers
38
views
Finding adjacent vertices on a convex polytope, searching among basis exchanges?
My question is about how, in general, to go from one vertex of a convex polytope to an adjacent one. But also I have more conceptual questions about how the simplex method works.
Say I have a linear ...
2
votes
2
answers
107
views
All quadrangulations on $14$ vertices
I am looking for a list of all quadrangulations on $14$ vertices. Is there a database anywhere for this?
0
votes
0
answers
10
views
Construct a point set with specific conditions
For every $n\geq 4$, construct a point set with $n$ points whose flip graph consists of two vertices connected by an edge. (collinear points are allowed).
I know that for a planar point set $S$, the ...
- 157
1
vote
0
answers
71
views
Finding all vertices, extremal rays, and extremal lines of a polyhedron
The following problem was given to me by a friend .
Find all vertices, extremal rays, and extremal lines of the following polyhedron. $$ P = \left\{ x ∈ \Bbb R^3 : 2x_1 − x_2 \ge 2, x_1 + x_2 \ge 1, −...
- 101
0
votes
0
answers
14
views
$4$-connected Eulerian triangulations $T$ such that $T-e$ is 3-degenerate for some edge $e$
Do there exist $4$-connected plane Eulerian triangulations $T$ such that there exists some edge $e\in E(T)$ such that the graph $T-e$ is 3-degenerate? I cannot find any examples of such graphs, but ...
18
votes
0
answers
223
views
Circles of radius $1, 2, 3, ..., n$ all touch a middle circle. How to make the middle circle as small as possible?
Non-overlapping circles of radius $1, 2, 3, ..., n$ all touch a middle circle. How should we arrange the surrounding circles, in order to minimize the middle circle's radius $R$?
Take $n=10$ for ...
- 8,378
14
votes
1
answer
307
views
Frame challenge: Find the maximum $n$ such that circles of radius $1, \frac12, \frac13, ..., \frac1n$ can be held immobile by a convex frame.
Find the maximum $n$ such that circles of radius $1, \frac12, \frac13, ..., \frac1n$ can be held immobile by a convex frame, or show that there is no maximum.
Here is an example with $n=7$.
By "...
- 8,378
25
votes
2
answers
533
views
What is the minimum area of a rectangle containing all circles of radius $1/n$?
What is the minimum area of a rectangle containing all (non-overlapping) circles of radius $1/n$, $n\in\mathbb{N}$ ?
The total area of the circles is finite: $\sum\limits_{n=1}^\infty \frac{\pi}{n^2}=\...
- 8,378
2
votes
0
answers
50
views
if deg(a)=0 in a graph, is "a" counted as an even vertex or not?
i was solving this test, and the answer of title affects the answer, so i was confused.
Q) in a simple graph, p=10 and 2q/p=3. the graph has 3 isolated vertices and all other vertices have a degree of ...
- 33
7
votes
1
answer
305
views
Coloring every point of the plane with 4 colors
Problem. If every point in the plane ($\mathbb{R}^2$) is colored either red, yellow, green, or blue, show that some two points are a distance of either $1$ or $\sqrt{3}$ apart and have the same color....
- 10.3k
1
vote
0
answers
36
views
Is the set of lines intersecting a line segment convex
I have been solving a problem that goes as follows:
If $F$ is a family of $n$ line segments on parallel lines and each triple can be intersected with a line then there is a line intersecting all the ...
- 405
5
votes
1
answer
124
views
The possible number of intersections of n lines
Suppose there are $n$ lines on a plane with no $3$ lines concurrent, such that they are not all parallel. What are the possibilities for the number of intersections of these lines?
I get that the ...
- 97
2
votes
1
answer
67
views
Sum of sizes of subsets which intersect at most one element
I have the following problem at hand (HW problem so please don't give me full solutions).
We have a set $N$ with $n$ elements and $M=\{M_1,M_2,\dots,M_n\}$ such that each two intersect at at most one ...
- 63
0
votes
0
answers
23
views
VC dimension of axis-parallel boxes
Let $A$ be the family of axis-parallel boxes in the $d$-dimensional unit cube $[0,1]^d$ having one vertex at the origin. It is known that the VC dimension of $A$ is $d$. Let $B$ be the family of all ...
user1041867
2
votes
1
answer
50
views
An infinite family of connected graphs with "few" edges and "many" crossing number.
I've been trying to construct a proof for this exercise but I don't know where to start:
Find an infinite family of connected graphs and universal constants
$c$ > 0 and $\epsilon$ > 0 such that ...
- 63
0
votes
0
answers
31
views
Is that two commutative elliptic isometry have at least one same fixed point？
I am reading the hyperbolic geometry by Martelli's book 《An Introduction to Geometry Topology》, the question is from p136 proposition 5.1.4's proof $ (3) \Rightarrow ( 4 ) $, it ask me to adapting ...
- 1
0
votes
0
answers
6
views
Difference set of sampled Fermat's spiral
In my research, I'm considering a regular discretization of Fermat's spiral. Let's call that set $\Lambda \subset \mathbb R^2$.
I was wondering if the properties (such as density, point multiplicities,...
2
votes
0
answers
24
views
Version of Helly theorem in the plane
This is a question from the book lectures on Discrete Geometry:
Let $C_1, \dots, C_n$ be convex sets in the plane such that each 4-tuple of them contains a ray in the intersection. Prove that $\...
- 405
0
votes
1
answer
26
views
Name for a figure bounded by algebraic sets
Is there an established named for the class of solid figures in $\mathbb{R}^n$ whose boundaries consist of finitely many sections of algebraic sets of codimension 1? Something like 'algebrotope' (and '...
1
vote
0
answers
22
views
On sufficient conditions for planar convex regions to be circular disks.
If C is a planar convex region and there is a point P on its boundary such that the perpendicular bisectors of all chords to C starting at P are concurrent, then, can we assert that C is necessarily a ...
- 147
0
votes
0
answers
24
views
Discretization of $\mathbb{R}^n$
I wish to find a specific discretization of $\mathbb{R}^n$ in such a way that the subsets obtained form hyperplanes of codimension 1. Let me explain:
If we consider a prime number $p$ then $\mathbb{Z}...
- 415
0
votes
0
answers
21
views
Proving lower bound on $n$-point set in dimensions $4$ and higher, for the number of unit distances.
I want to use the analogous problem of unit distances among n points in $R^{3}$, that Erdos proved $\Omega\left ( n^{4/3}\log\log n \right )$ from below and $O\left ( n^{5/3} \right )$ from above, to ...
user1041867
0
votes
1
answer
86
views
How to determine whether a given convex polytope is contained in another given convex polytope?
Given a tall matrix $A \in \mathbb{R}^{m \times n}$ (where $m > n$) and a vector $b\in\mathbb{R}^{m}$, we say that they define the set $$\mathcal{S} = \left\{x\in\mathbb{R}^n: Ax\le b\right\}$$ ...
- 2,077
1
vote
0
answers
34
views
Existance of a point cutting a shape into big parts
As discussed in comments of this question I am opening a new question about this specific problem:
Given a closed polygon $P$, of area $S(P)$ find a point $x\in \mathbb{R}^2$ such that every line ...
- 330
1
vote
1
answer
92
views
Maximum volume inside a convex polyhedron
For a rectangle $\mathcal R = \{ x \in R^n \mid l \preceq x \preceq u \}$ of maximum volume to be enclosed in polyhedron $\mathcal P = \{ x \mid Ax \preceq b \}$, according to Stephen Boyd's EE364a ...
- 173
0
votes
1
answer
46
views
Inradii of convex polytopes
Consider a convex polytope $P$ in $\mathbb{R}^n$ with nonempty interior. Let $r(P)$ denote the inradius of $P$, that is, the radius of the sphere contained in $P$ which touches all facets of $P$, ...
- 193
2
votes
2
answers
74
views
Proof request: every polytope has a facet
When I was reading Ziegler's book "Lectures on Polytopes" this statement appeared to be never proven formally.
Question: does every (convex, bounded, non-empty) polytope have a facet?
Here ...
- 29k
2
votes
1
answer
98
views
Intersecting $B^d_\infty$ with the hyperplane $H = \{x\in \Bbb R^d: x_1 + \ldots + x_d = 0\}$
The following problem appears in Section $2.3$ (Exercise $13$) of these notes on Convex and Discrete Geometry (see Pg. $16$).
Consider the following vertices of $B_\infty^4 := \{x\in \Bbb R^4: \|x\|_\...
- 11.4k
0
votes
0
answers
12
views
Under which circumstances does a polyhedron have at least one vertex?
for a totally unimodular matrix $A$ and a vector $b$ denote the polyhedron $P:=\lbrace x | Ax \leq b \rbrace$. I was wondering if there exists a criterion that states under which conditions $P$ has at ...
- 652
1
vote
1
answer
115
views
Number of extreme points of a convex polyhedron
In $\mathbb{R}_+^n$ $(n\geq 1)$, let $S$ be the $(n-1)$-simplex:
$$S=\left\{x\in\mathbb{R}_+^n,\,\sum_{i=1}^n x_i=1\right\}$$
whose relative interior is denoted $\mathring S$, and $E$ be a linear ...
- 145
0
votes
0
answers
46
views
Why do these solution graphs not match each other?
Consider the Initial Value Problem, $\frac{dP}{dt} = ((1 + f)^\frac{3}{5} (1 - f)^\frac{2}{5} - 1)P,\ P(0) = 100$, where $f$ is a real parameter between $0$ and $1$, inclusive. Its solution is $P = ...
- 1,554
1
vote
1
answer
64
views
Finding the 2-facets of a convex 4D polytope (algorithm)
I'm an undergraduate student and I'm currently working on my end-of-degree-project. The main goal of this project is studying the $A_4$ root lattice, the geometry of its Voronoï complex, and using the ...
- 11
0
votes
0
answers
30
views
``Quantum''/ non-commutating extension of polytopes
Are there non-commutative (ie. quantum) extensions of polytopes?
More specifically I was wondering if there are some deformation, say $\hbar$, to polytopes which when is taken to be zero, one gets ...
- 171
1
vote
1
answer
24
views
Does there exist Eulerian quadrangulations that are not 1- or 2-degenerate?
I am looking for Eulerian planar quadrangulations that are not 1- or 2-degenerate, but I cannot seem to find such graphs.
Note: a graph is Eulerian if and only if every vertex has an even degree. ...
user931598
1
vote
0
answers
62
views
Diameter of a Cartesian product of two graphs
If I am looking at a Cartesian product of two graphs $G_1$ and $G_2$ (defined here https://en.wikipedia.org/wiki/Cartesian_product_of_graphs).
I am trying to bound the diameter of the graph $G_1 \...
- 63
0
votes
0
answers
29
views
Possibility of non-intersecting chord diagrams with given sets of endpoints
Consider two finite subsets of a circle, $A,B \in S^1$, each with even number of elements. I want to construct two chord diagrams, one with endpoints set $A$, and one with endpoints set $B$ in such a ...
- 1
1
vote
0
answers
59
views
Every $\mathcal{V}$-polyhedron is an $\mathcal{H}$-polyhedron
On page 32 of Ziegler's lectures, he wants to show that every $\mathcal{V}$-polyhedron is an $\mathcal{H}$-polyhedron. Ziegler defines the $\mathcal{V}$-polyhedron as the Minkowski sum of a convex ...
- 469
1
vote
0
answers
24
views
(2,3,7) tiling of Hurwitz surface
I'm reading through the paper On the Geometry of Hurwitz Surfaces for an undergraduate project. Apologies for my basic questions; I've not met these ideas before.
In the abstract, the source says:
By ...
- 51
0
votes
1
answer
35
views
Simplify algebraic vector expressions with dot product and cross product
I am trying to derive the bending force of a discrete curve, which requires the derivative of angles between two vectors represented tangent half angle. I follow this note for my derivation: https://...
Dowbee
1
vote
1
answer
40
views
Group of isometries acting on a metric space is already discrete if a stabilizer is finite and an orbit is discrete
My question is on page 163, the proof of Lemma 7 in the book Foundations of hyperbolic manifolds by John G. Ratcliffe.
Let $\Gamma$ be a group of isometries of a metric space $X$. If there is a point $...
- 717
4
votes
1
answer
79
views
What Is The Most Efficient Way To Tile A Page With Cube Nets?
I'm trying to print out nets of a cube on a sheet of paper, and I'm hoping to fit as many as I can on single sheets. The squares that make up the net are $\frac{1}{2}$ an inch wide, and I'm printing ...
- 53