Questions tagged [discrete-geometry]

Finite or discrete collections of geometric objects. Packings, tilings, polyhedra, polytopes, intersection, arrangements, rigidity.

Filter by
Sorted by
Tagged with
5 votes
1 answer
111 views

Finding the point within a convex n-gon that maximizes the least angle subtended there by an edge of the n-gon

For any point P in the interior of a convex polygon, the sum of the angles subtended by the edges of the polygon is obviously 2π. Given a convex polygon, how does one algorithmically find the point (...
1 vote
0 answers
14 views

Finding the point within a convex n-gon that minimizes the largest angle subtended there by an edge of the n-gon

This post records a variant to the question asked in this post: Finding the point within a convex n-gon that maximizes the least angle subtended there by an edge of the n-gon Given a convex n-gon, ...
0 votes
0 answers
49 views

An algorithm to decide whether a convex polygon can be cut into 2 mutually congruent pieces

This post is based on the answer to this question: A claim on partitioning a convex planar region into congruent pieces A perfect congruent partition of a planar region is a partition of it with no ...
0 votes
0 answers
23 views

Is there a variant of the crossing lemma for multigraphs with arbitrary embedding?

Suppose $G$ is a graph with $m=|E(G)|$ edges and $n=|V(G)|$ vertices. Suppose $sim(G)$, the simplification of $G$ contains $ m' >> 3n $ edges. Call the set of edges corresponding to an edge $uv$...
1 vote
0 answers
75 views

To tile the plane with mutually non-congruent rational triangles of equal area

We add a little to Tiling the plane with pairwise non-congruent rational triangles Question: Can the plane be tiled by pair-wise non-congruent rational triangles all of which have same area? If "...
1 vote
1 answer
198 views

On comparing planar convex regions of equal perimeter and area

Definitions: The Hausdorff distance between two point sets is the greatest of all the distances from a point in one set to the closest point in the other set. Given two planar convex regions $C_1$ ...
2 votes
0 answers
75 views

"separators" for nonplanar graphs embedded in the plane

Given a nonplanar graph $G$ drawn in the plane with crossings. Does there exist a small subset $S$ of edges of $G$ such that after the removal of all edges that intersect or share an endpoint of an ...
1 vote
1 answer
215 views

Positioning a member of an interval partition

Let $\ 0<\Lambda_1\le\ldots\le\Lambda_n\ $ be a finite non-decreasing sequence of positive reals, of length $\ n>0.\ $ Let $$ D:=\sum_{k=1}^n \Lambda_k $$ The question is about the conditions ...
11 votes
0 answers
308 views

Is a convex polyhedron determined by its edge lengths and angular defects?

Let's consider 3-dimensional convex polyhedra $P\subset\Bbb R^3$. The angular defect at a vertex $v$ is $2\pi$ minus the sum of the interior angles of the incident faces at $v$. Question: Is a ...
2 votes
1 answer
130 views

Do the dual graphs of hyperplane arrangements admit Hamiltonian paths?

Consider a simple hyperplane arrangement $H_1,\cdots,H_n$ in the Euclidean space $\mathbb{R}^d$. By "simple" we mean any $k$ hyperplanes in $\{H_1,\cdots,H_n\}$ intersect in codimension $k$. ...
4 votes
1 answer
414 views

Counting number of points on a lattice in a hypercube

Suppose I have a lattice $\Lambda \in \mathbb{R}^n$. Let $X_i >0$ for $i=1,..,n$. I am interested in some references regarding counting number of points of $\Lambda$ inside $[-X_1, X_1] \times \...
8 votes
1 answer
250 views

A claim on partitioning a convex planar region into congruent pieces

Let us define a perfect congruent partition of a planar region $R$ as a partition of it with no portion left over into some finite number n of pieces that are all mutually congruent (ie any piece can ...
1 vote
0 answers
38 views

Polyhedra inscribed in a sphere with mutually non-congruent, equal area faces

Two constrained versions of the main question given in this post: Polyhedrons with mutually non-congruent faces, all of equal area. An earlier post that could be related: Cutting a spherical surface ...
3 votes
1 answer
185 views

Exponential growth of shortest vector norm for successive lattices corresponding to powers of a matrix

Let $A\in M_{2\times 2}(\mathbb{Z}) $ be a two by two integer matrix such that $0,\pm 1$ are not eigenvalues of $A$ and $\left|\det(A)\right|>1$. I am interested in the growth of the norm shortest ...
5 votes
1 answer
387 views

Computational approach deciding whether a set of Wang Tile could tile the space up to some size

As an applied person, I'm facing one practical problem deciding whether a set of Wang tile could tile the plane periodically or aperiodically. Although both problems seem undecidable, but I'm on a ...
4 votes
0 answers
104 views

Hyponontiling Wang tiles

Call a finite collection of tiles that can tile the plane if we have to use each tile at least once tiling. Is there a collection of at least 3 tiles that is not tiling, but such that after removing ...
1 vote
0 answers
82 views

Polyhedrons with mutually non-congruent faces, all of equal area

This question is closely related to Convex polyhedra with non-congruent faces It is known that if all faces of a tetrahedron ought to have same area (or same perimeter), then, the faces are ...
1 vote
0 answers
28 views

Finite right-triple convex sets in planes

Let $\mathcal{S}$ be a set of points in $\mathbb{R}^2$. We say that $\mathcal{S}$ is right-angle convex, if for any two distinct points $P,Q\in \mathcal{S}$ there always exists another point $R\in \...
18 votes
1 answer
1k views

Does a function from $\mathbb R^2$ to $\mathbb R$ which sums to 0 on the corners of any unit square have to vanish everywhere?

Does a function from $\mathbb{R}^2$ to $\mathbb{R}$ which sums to 0 on the corners of any unit square have to vanish everywhere? I think the answer is yes but I am not sure how to prove it. If we ...
10 votes
1 answer
259 views

Do triple-linked graphs exist?

Lets say that a finite simple graph $G$ is (intrinsically) fully triple-linked if for each embedding of $G$ into $\Bbb R^3$ we can find three disjoint cycles $C_1,C_2,C_3\subset G$ whose embeddings ...
16 votes
0 answers
289 views

Realization spaces of 3-dimensional polytopes with fixed face areas

It is a well-know result (Steinitz, 1922) that the realization space of 3-dimensional convex polytopes with fixed combinatorics is contractible. A proof of this theorem can be found for instance in ...
0 votes
0 answers
69 views

Heronian tetrahedra with pairwise non-congruent, equal area faces

Reference: https://mathworld.wolfram.com/HeronianTetrahedron.html lists some Heronian tetrahedra that are disphenoids. Are there any Heronian tetrahedra with all faces having same area but are ...
1 vote
1 answer
106 views

Recognizability/unique composition property for substitution tiling

This may be a very basic question, but I have not found an answer to it so far in my search. The question is whether there is an "algorithmic" way to check unique-composition/recognizability ...
1 vote
0 answers
90 views

A claim on the largest area circular segment that can be drawn inside a planar convex region

This post adds a little to To find the longest circular arc that can lie inside a given convex polygon A circular segment is formed by a chord of a circle and the line segment connecting its endpoints....
28 votes
3 answers
2k views

Is the ratio Perimeter/Area for a finite union of unit squares at most 4?

Update: As I have just learned, this is called Keleti's perimeter area conjecture. Prove that if H is the union of a finite number of unit squares in the plane, then the ratio of the perimeter and ...
3 votes
1 answer
670 views

Infinite dimensional lattice for integers and the Riemann hypothesis?

It is known that for each finite set of primes $p$ we have: $\log(p)$ are linear independent over the rational numbers. We have $\log(ab) = \log(a)+\log(b)$ and $\log(n) = \sum_{p |n}v_p(n) \log(p)$. ...
1 vote
1 answer
87 views

To place copies of a planar convex region such that number of 'contacts' among them is maximized

A contact between two planar convex regions obviously happens either along a line segment or at a single point. Question: Given a planar convex region $C$ and a number $n$, we need to lay out $n$ ...
15 votes
4 answers
844 views

Tiling a rectangle with all simply connected polyominoes of fixed size

For which values of $n$ can we tile some rectangle with one copy of each free simply-connected $n$-omino (that is, each polyomino with $n$ squares that has no holes)? It appears that it is possible ...
2 votes
1 answer
165 views

Estimating ${\left(\sum_{i=j}^k {x_i}\right)^2} \times \left\lvert\sum_{i=j}^k {a_i}\right\rvert$

Given two sets; $X = \{x_i : x_i \geq 0; i \in [\sqrt{n}]\}$ and $A = \{a_i : |a_i| \leq 1; i \in [\sqrt{n}]\}$ of size $n^{\frac{1}{2}}$ each, with the following properties \begin{equation}\label{...
12 votes
2 answers
959 views

Drawing 3-configurations of points and lines with straight lines

It is well-known that the black-and-white coloring of the Heawood graph on 14 vertices determines a combinatorial 3-configuration with 7 "points" and 7 "lines", known as Fano plane....
67 votes
3 answers
11k views

Nonconvexity and discretization

Edit: Here's a more down-to-earth, and somewhat weakened, but I believe still nontrivial, version of the main theorem. Prototypical nonconvex spaces are $\ell^p$-spaces for $0<p<1$, say $\ell^p(\...
2 votes
1 answer
95 views

Exhaustive list of small graphs for which $\frac{\alpha(G)\omega(G)}{n}$ is small?

I am looking for a list of small graphs (say on less than 10 vertices) for which the parameter $p(G) = \frac{\alpha(G) \omega(G)}{n}$ is small. Here $\alpha(G)$ and $\omega(G)$ is the size of the ...
5 votes
1 answer
139 views

Given a 3-connected graph $G$, is there an edge $e$ so that both $G-e$ and $G/e$ are still 3-connected?

Let $G$ be a 3-connected (simple) graph other than $K_4$. In Diestel's "Graph Theory" Section 3.2 we find Lemma 3.2.2. There is an edge $e$ so that $G\mathbin{\dot-}e$ is still 3-connected (...
1 vote
1 answer
57 views

To maximize the volume of the polyhedron resulting from perimeter-halvings of a convex polygonal region

We add one more bit to Forming paper bags that can 'trap' 3D regions of max surface area (note: some possibly open related questions are also in the comments following the answer to above ...
2 votes
0 answers
116 views

Folding polygons into 'vessels'

This question is based on http://www.science.smith.edu/~jorourke/Papers/FoldingPP.pdf Define an vessel as a convex polyhedron with one face removed - in other words, a vessel can be converted into a ...
7 votes
0 answers
128 views

How many simplicial spheres with $n$ vertices and $N$ facets?

Let $s_d(n,N)$ be the number of different $d$-dimensional simplicial spheres on $n$ labelled vertices and $N$ facets (= $d$-simplices). I am in search for the best know upper bounds, especially for $d\...
2 votes
1 answer
165 views

Forming paper bags that can 'trap' 3D regions of max surface area

An existence question based on 'Trapping' 3D regions with sheets of paper. Given a sheet of paper S that is a planar convex region, one tries to form a 'closed bag' that contains a connected ...
0 votes
0 answers
46 views

Which planar convex region with specified area and perimeter maximizes/minimizes Moment of Inertia?

By moment of inertia of a planar convex region C, here we mean its moment of inertia about an axis passing through the center of mass of C and perpendicular to the plane of C. Question: For specified ...
3 votes
1 answer
436 views

On some infinite planar arrangements with triangles

Background: Given a convex region C. One can define a graph corresponding to a planar arrangement of non overlapping congruent copies of C - each unit C is a node and an edge connects it to another ...
22 votes
2 answers
878 views

Is every 1-million-connected graph rigid in 3D?

It is an old result that every $6$-connected graph is rigid in $\mathbb{R}^2$: Lovász, László, and Yechiam Yemini. "On generic rigidity in the plane." SIAM Journal on Algebraic Discrete ...
0 votes
1 answer
121 views

On 'special' points on uniform planar convex regions defined in terms of moment of inertia

The following can be easily proved using perpendicular axes theorem and intermediate value theorem: Lemma: Given any uniform planar convex region $C$ and any point on it, $P$, there will be at least ...
2 votes
1 answer
194 views

Cutting convex regions into equal diameter and equal least width pieces

The diameter of a convex region is the greatest distance between any pair of points in the region. The least width of a 2D convex region can be defined as the least distance between any pair of ...
0 votes
0 answers
69 views

On 'Width Equalizers' of planar convex regions

Definitions: The least width of a 2D convex region C is the least distance between any pair of parallel lines that both touch the boundary of C (in what follows, we refer to this quantity as simply '...
6 votes
1 answer
281 views

Covering number estimates on closed Riemannian manifolds

Let $(M^n,g)$ be an $n$-dimensional compact and connected Riemannian manifold with sectional curvature bounded above and below by $c,C$. Is it possible/known how to express the external covering ...
3 votes
0 answers
87 views

Minkowski problem for polytopes: the origin of necessary condition

Minkowski's uniqueness theorem for polytopes concerns the specification of the shape of a polytope by the directions and measures of its facets. Theorem (Minkowski). Let $A_i$ be positive faces areas ...
21 votes
0 answers
434 views

Does every 5-celled animal tile the plane?

An animal in the plane is a finite set of grid-aligned unit squares in $\mathbb{R}^2$. (The definition is the same as a polyomino, but where we relax the connectivity requirement.) One may ...
38 votes
3 answers
2k views

Is there a regular pentagon with a rational point on each edge?

This question was asked by Yaakov Baruch in the comments to the question Can a regular icosahedron contain a rational point on each face? It seems that this question deserves special attention.
3 votes
2 answers
758 views

Kepler conjecture: Are there only two most efficient packings or could there be more than two?

Today I attended a talk by Terence Tao, attended by (I'm guessing) probably at least a couple of thousand people, in which among other things he said it had been proved that no packing of spheres in ...
3 votes
0 answers
112 views

Reference request: Carathéodory-type theorem for convex hulls of closed sets

I'm looking for a reference for the following theorem. Theorem Let $X$ be a closed subset of $\mathbb{R}^N$, and let $a$ be a point of its convex hull $\operatorname{conv}(X)$. Then there exist ...
13 votes
3 answers
414 views

Maximal distance between $2d+1$ points on the $(d-1)$-sphere

If one arranges $2d$ points on the sphere $\mathbf S^{d-1}\subset\Bbb R^d$ at the vertices of the crosspolytope, then one can achieve a minimal spherical distance of $\pi/2$ between any two points, ...

1
2 3 4 5
37