Questions tagged [discrete-geometry]

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

Filter by
Sorted by
Tagged with
4 votes
1 answer
74 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 (...
Nandakumar R's user avatar
  • 5,451
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$...
Hao S's user avatar
  • 181
2 votes
0 answers
74 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 ...
Hao S's user avatar
  • 181
0 votes
0 answers
43 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 ...
Nandakumar R's user avatar
  • 5,451
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$. ...
YHBKJ's user avatar
  • 3,127
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 ...
Nandakumar R's user avatar
  • 5,451
4 votes
0 answers
103 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 ...
domotorp's user avatar
  • 18.3k
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 ...
Nandakumar R's user avatar
  • 5,451
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 \...
Joe Zhou's user avatar
  • 123
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 ...
Ivan Meir's user avatar
  • 4,782
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 ...
M. Winter's user avatar
  • 12.5k
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 ...
Nandakumar R's user avatar
  • 5,451
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)$. ...
mathoverflowUser's user avatar
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 ...
M. Winter's user avatar
  • 12.5k
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{...
Krish's user avatar
  • 23
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 ...
Agile_Eagle's user avatar
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 (...
M. Winter's user avatar
  • 12.5k
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$ ...
Nandakumar R's user avatar
  • 5,451
1 vote
1 answer
56 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 ...
Nandakumar R's user avatar
  • 5,451
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....
Nandakumar R's user avatar
  • 5,451
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\...
M. Winter's user avatar
  • 12.5k
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 ...
Nandakumar R's user avatar
  • 5,451
2 votes
1 answer
164 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 ...
Nandakumar R's user avatar
  • 5,451
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 '...
Nandakumar R's user avatar
  • 5,451
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 ...
Tom Leinster's user avatar
  • 27.2k
0 votes
0 answers
58 views

Comparing partitions of a given planar convex region into pieces with equal perimeter and pieces of equal width

We continue from Cutting convex regions into equal diameter and equal least width pieces. There we had asked for algorithms to partition a planar convex polygon into (1) $n$ convex pieces of equal ...
Nandakumar R's user avatar
  • 5,451
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 ...
Alexey Ustinov's user avatar
2 votes
0 answers
83 views

Computationally decomposing a complete geometric graph into forests of stars

I'm working on the following problem: I would like to see if it possible to decompose a complete geometric graph on $8$ vertices into $5$ planar star-forests. As doing this by hand was hopeless, I ...
Jeja's user avatar
  • 21
1 vote
0 answers
185 views

Local to global complexity of triangulations

Alright 3rd time's the charm - editing again to put all my cards on the table. Consider a PL $n$-manifold $M$. Define the complexity $c(M)$ of $M$ to be the minimum number of $n$-simplices needed to ...
rab's user avatar
  • 139
1 vote
0 answers
74 views

Dissection of polygons into triangles with least number of intermediate pieces

This wiki article: https://en.wikipedia.org/wiki/Wallace%E2%80%93Bolyai%E2%80%93Gerwien_theorem shows the dissection of a square into a triangle via 4 intermediate pieces. It appears easy to form a ...
Nandakumar R's user avatar
  • 5,451
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 ...
Michael Hardy's user avatar
2 votes
1 answer
96 views

Another lemma on intersections of $d$-simplices

Let $d\ge1$. A $d$-simplex $S$ is the convex hull in $\mathbb R^d$ of the vertices $v_0,\dots,v_d\in\mathbb R^d$ where $\{v_1-v_0,\dots,v_d-v_0\}$ is a linearly independent set of $d$ vectors; for ...
Tri's user avatar
  • 1,366
1 vote
0 answers
40 views

Are there rectangles that can be cut into non-right triangles that are pair-wise similar and pair-wise non-congruent?

We generalize the questions of Can a square be cut into non-right triangles that are mutually similar and pair-wise noncongruent? Can any rectangle be cut into some finite number of triangles that ...
Nandakumar R's user avatar
  • 5,451
1 vote
0 answers
89 views

Can a square be cut into non-right triangles that are mutually similar and pair-wise noncongruent?

We add a bit to Tiling the plane with pair-wise non-congruent and mutually similar triangles and Cutting polygons into mutually similar and non-congruent pieces A (non square) rectangle can obviously ...
Nandakumar R's user avatar
  • 5,451
2 votes
1 answer
88 views

A lemma on intersections of $d$-simplices

I have searched in vain for a combinatorial proof of Sperner's Lemma that rigorously proves the following: Let $d\ge0$. A $d$-simplex is the convex hull in $\mathbb R^d$ of the vertices $v_0,\dots,...
Tri's user avatar
  • 1,366
4 votes
0 answers
170 views

Can a square be partitioned into mutually non-congruent triangles all of same area and perimeter?

It is known that the plane cannot be tiled by pair-wise non-congruent triangles all having same area and same perimeter (https://arxiv.org/abs/1711.04504). Question: Can a square be partitioned into ...
Nandakumar R's user avatar
  • 5,451
1 vote
3 answers
200 views

A rational distance problem with (possibly) multiple solutions

Background: It is not known if any point exists on the XY plane that is at rational distance from all 4 vertices of a unit square lying on the XY plane (https://mathworld.wolfram.com/...
Nandakumar R's user avatar
  • 5,451
4 votes
0 answers
210 views

Economic equilibrium and tropical geometry

There is a famous saying in economics: When everyone pursues his or her own interests, there is an invisible hand that brings the market to equilibrium. However, this is not always the case. Here is ...
Surpass2019's user avatar
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 "...
Nandakumar R's user avatar
  • 5,451
1 vote
0 answers
105 views

Which polygons allow partition into rational triangles?

A triangle with all side lengths rational is said to be a rational triangle. It is known - for example, Cutting the unit square into pieces with rational length sides - that the unit square allows ...
Nandakumar R's user avatar
  • 5,451
20 votes
1 answer
905 views

Conjecture: Given any five points, we can always draw a pair of non-intersecting circles whose diameter endpoints are four of those points

The following question resisted attacks at Math SE, so I thought I would try posting it here. Is the following conjecture true or false: Given any five coplanar points, we can always draw at least ...
Dan's user avatar
  • 2,341
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.
Alexey Ustinov's user avatar
4 votes
0 answers
302 views

Regular solids and $\mathbb{Z}_5$

The mapping from the regular solids to $\mathbb{Z}_5$ given by the number of faces in the solid mod 5, interestingly, is a bijection. Any geometers or algebraists know if there is a significant ...
David I. McIntosh's user avatar
2 votes
1 answer
103 views

To find the convex planar region minimizing diameter when area and perimeter are given

The basic question is to find that planar convex region for which diameter is a minimum when area and perimeter are specified. A partial answer is given here: http://nandacumar.blogspot.com/2012/11/...
Nandakumar R's user avatar
  • 5,451
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 ...
Nandakumar R's user avatar
  • 5,451
2 votes
0 answers
62 views

Is this an actual solution for centroidal Voronoi tiling, or just a visual approximation? [closed]

For the capstone project at the end of my graduate Data Science studies in late 2022, I needed an algorithm that would converge to something close to centroidal Voronoi tiling, while tiling contiguous ...
Florin Andrei's user avatar
1 vote
0 answers
60 views

Embedding toric varieties in other toric varieties as a real algebraic hypersurface

In the question On a Hirzebruch surface, I've seen that the $n$-th Hirzebruch surface is isomorphic to a surface of bidegree $(n,1)$ in $\mathbb{P}^1\times \mathbb{P}^2$. I am trying to answer the ...
Yromed's user avatar
  • 63
2 votes
1 answer
132 views

On the moment of inertia of planar convex regions and possible special nature of circular disks

We consider uniform convex planar regions and lines through their center of mass and lying in the same plane as the region; each line is parametrized by an angle $\alpha$ it makes with some reference ...
Nandakumar R's user avatar
  • 5,451
11 votes
1 answer
388 views

Smallest sphere containing three tetrahedra?

What is the smallest possible radius of a sphere which contains 3 identical plastic tetrahedra with side length 1?
trionyx's user avatar
  • 111
6 votes
1 answer
226 views

Do lattices of small co-volume always exist in rational, connected, simply connected, nilpotent Lie groups?

Given a connected, simply connected, rational, nilpotent Lie group $G$, is there a lattice of arbitrarily small co-volume in $G$? If $G$ is Carnot, the answer is "yes" by applying a ...
Kyle's user avatar
  • 243

1
2 3 4 5
34