Questions tagged [discrete-geometry]

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

Filter by
Sorted by
Tagged with
10 votes
3 answers
481 views

Given the skeleton of an inscribed polytope. If I move the vertices so that no edge increases in length, can the circumradius still get larger?

Let $P\subset \Bbb R^n$ be an inscribed convex polytope, that is, all its vertices are on a common sphere of radius $r$. Let $G$ be the edge-graph of $P$. For convenience, assume $V(G)=\{1,\dotsc,s\}$....
M. Winter's user avatar
  • 12.5k
4 votes
0 answers
54 views

On ways to measure the difference between two planar convex regions

This earlier post attempted to quantify the difference between a pair of planar convex regions of equal area and perimeter using Hausdorff distance: On comparing planar convex regions of equal ...
Nandakumar R's user avatar
  • 5,401
3 votes
1 answer
131 views

Finding the smallest centrally symmetric region that contains a convex planar region

Given a convex polygonal region C, how does one find/characterize the smallest zonogon (centrally symmetric convex polygon https://en.wikipedia.org/wiki/Zonogon) that contains C? Note 1: In question ...
Nandakumar R's user avatar
  • 5,401
1 vote
0 answers
72 views

A ratio to measure 'roundedness' of planar convex regions

Ref: A center of convex planar regions based on chords The above discussion quotes the definition of 'centralness coefficient' and defines a center of a planar convex region. 1/2 is the least possible ...
Nandakumar R's user avatar
  • 5,401
2 votes
0 answers
71 views

On cutting convex regions with average values of quantities minimized

This post continues from Cutting convex regions into equal diameter and equal least width pieces - 2 and Cutting convex regions into equal diameter and equal least width pieces - 3 A basic (and to my ...
Nandakumar R's user avatar
  • 5,401
4 votes
0 answers
121 views

Find a good drawing for the edges of any two component of $G-S$ that do not cross

A drawing of a graph $G$ on the plane $P$ is a representation of $G$, where vertices are distinct points in $P$, and edges are Jordan arcs in the plane joining the points corresponding to their end ...
L.C. Zhang's user avatar
  • 1,605
8 votes
1 answer
400 views

What should a meaningful notion of curvature satisfy, in the absence of a smooth structure?

There are many generalizations of various curvatures to non-smooth metric spaces (e.g. Ollivier's Ricci curvature). Suppose I have a metric space $(X,d)$ and I want to define a notion of curvature ...
Brendan Mallery's user avatar
3 votes
0 answers
69 views

On possible generalizations of the Steiner ellipse – convex regions containing and contained within a given convex quadrilateral

In the post On convex regions containing (and contained within) a given triangle , it was noted: for a general triangle $T$, the convex region $C_M$ of largest area containing $T$ such that $T$ is ...
Nandakumar R's user avatar
  • 5,401
3 votes
2 answers
201 views

Partition of polygons into 'congruent sets of polygons'

Definition: Two finite sets of polygons $A$ and $B$ are congruent if we can match polygons in $A$ in a one-one manner with polygons in $B$ with each matched pair of polygons mutually congruent. ...
Nandakumar R's user avatar
  • 5,401
0 votes
0 answers
81 views

Perfectly balanced spanning trees

I call a spanning tree perfectly balanced if, after a two-coloring of the tree-graph's vertices the two vertex sets that are defined by the assigned colors have equal cardinality and the two vertex ...
Manfred Weis's user avatar
  • 12.6k
3 votes
1 answer
223 views

Least area and least perimeter triangles that contain a convex planar region - how different can they be?

Is there a planar convex region whose enclosing triangles of least perimeter and least area have different areas and different perimeters? And if so, which region maximizes the difference between the ...
Nandakumar R's user avatar
  • 5,401
2 votes
1 answer
78 views

What is the average component size of a coloring?

Supose each cell of a big (or infinite) grid is colored at random by one of $k$ colors. Then the connected monochromatic components (here components are not supposed to contain "wasp waists",...
Wolfgang's user avatar
  • 13.2k
9 votes
1 answer
347 views

Tiling the plane with finitely many congruent pieces

Suppose $A_1,\dots,A_n$ are measurable subsets of the plane that are all related by rigid motions such that $|(A_1 \cup \dots \cup A_n)^c| = 0$ and $|A_i \cap A_j| = 0$ for all $1 \leq i < j \leq n$...
James Propp's user avatar
  • 19.4k
1 vote
0 answers
30 views

On partitioning n-gons into pieces with reflection symmetry

Is 3(n-2) a tight lower bound on the least number of reflection symmetric pieces that any general n-gon can be cut into? What if we consider only convex n-gons? A kite is a reflection symmetric ...
Nandakumar R's user avatar
  • 5,401
13 votes
3 answers
651 views

Are there Monohedra with odd numbers of faces?

A monohedron is a convex polyhedron with all faces mutually congruent but with no other symmetry necessarily needed. So obviously, this is a wide class of polyhedra that includes the Platonic solids ...
Nandakumar R's user avatar
  • 5,401
3 votes
0 answers
118 views

Oscillator in Langton's ant

First of all, see Langton's ant Wikipedia page. If we place a pair of ants looking north (using Golly or any another prog) on the coordinates $(x_1,y_1)$ and $(x_2,y_2)$ under the conditions: $p=|x_1-...
Notamathematician's user avatar
5 votes
2 answers
305 views

Dimension of configuration space of triangulated convex polyhedron

The configuration space of all tetrahedra is $5$-dimensional, perhaps a non-obvious fact. There are $12$ face angles, but the sum of each of the four faces angles is $\pi$, reducing $12$ to $8$ ...
Joseph O'Rourke's user avatar
2 votes
1 answer
146 views

Packing densities of non-centrally symmetric planar convex regions

Reference: https://en.wikipedia.org/wiki/Smoothed_octagon Background: The smoothed octagon is conjectured to have the lowest maximum packing density of the plane of all centrally symmetric convex ...
Nandakumar R's user avatar
  • 5,401
3 votes
0 answers
274 views

Polyhedrons and their centers of mass

Given a convex polyhedron, one considers 3 possibilities: wireframe - only the edges of the polyhedron have mass which is uniformly distributed. surface - only the surface is massive with uniform ...
Nandakumar R's user avatar
  • 5,401
2 votes
0 answers
61 views

Rigid monohedral tilers

Say that a tile $T$ that alone can tile the plane—a monohedral tile—is rigid if it is not the case that $T$ can be slightly deformed to $T'$ so that: $T'$ can also tile the plane $T'$ is arbitrarily ...
Joseph O'Rourke's user avatar
1 vote
1 answer
501 views

Has this curious "duality" of weighted $K_4$ already been noticed?

A complete symmetric graph with $n=4$ vertices, i.e. a $K_4$ is the disjoint union of three perfect matchings $M_{\text{min}},M_{\text{mid}},M_{\text{max}}$ of which $M_{\text{min}}$ denotes the ...
Manfred Weis's user avatar
  • 12.6k
24 votes
1 answer
590 views

Polytope where each vertex belongs to all but two facets

Let $P$ be a (convex, bounded) polytope with the following property: for every vertex $v$, there are exactly two facets which do not contain $v$. Does it follow that $P$ is (combinatorially) a ...
Guillaume Aubrun's user avatar
1 vote
0 answers
52 views

Shadows and planar sections of polyhedra – 2

This post continues Shadows and planar sections of polyhedra and On planar sections of 3D convex bodies Shadows and planar sections of polyhedra gives an example demonstrating that shadows (orthogonal ...
Nandakumar R's user avatar
  • 5,401
4 votes
1 answer
207 views

Shadows and planar sections of polyhedra

By shadow we mean the orthogonal projection of a convex 3D body P onto a 2D plane, for example, the shadow on the xy-plane, with P above (z>0) that plane and the light at L=(0,0,+∞). P an be freely ...
Nandakumar R's user avatar
  • 5,401
2 votes
0 answers
102 views

A Variant of the Malfatti Problem

See the Wikipedia entry on Malfatti circles for an introduction to Malfatti's problem. The above page also states that for $n >3$, the question of whether a greedy method (at each step, the method ...
Nandakumar R's user avatar
  • 5,401
5 votes
1 answer
130 views

Embedding linklessly embeddable graphs without Borromean rings

A linklessly embeddable graph is a graph which can be embedded into $\Bbb R^3$ so that no two of its cycles are linked. For example, the Petersen graph is not such a graph. Now, I can think of another ...
M. Winter's user avatar
  • 12.5k
5 votes
2 answers
227 views

On intersections of several convex regions

Question: Given n convex planar regions. Required to place them (in suitable position and orientation) so that that part of the plane lying under all the regions (their common intersection) is of ...
Nandakumar R's user avatar
  • 5,401
9 votes
1 answer
282 views

Partitioning a set of lattice points in the plane into rectangles

The "long comment" by Pietro Majer on Reference for puzzle on dividing piles and scoring products suggests the following problem. Let $S$ be a finite subset of $\mathbb{Z}\times \mathbb{Z}$. ...
Richard Stanley's user avatar
7 votes
0 answers
223 views

Set of unit vectors such that among any three there is an orthogonal pair

I was fascinated by the solutions of Problem 8 of the IMC 2021 contest, which can be summarized as: Theorem 1. Let $v_1,\dotsc,v_N$ be distinct unit vectors in $\mathbb{R}^n$ such that among any three ...
GH from MO's user avatar
  • 97.8k
5 votes
2 answers
292 views

Tiling a Jordan polygon

I saw this problem some years ago, don't remember the source: Let $P$ be a Jordan polygon (i.e. the only points of the plane belonging to two edges are the polygon vertices) that can be tiled with ...
jack's user avatar
  • 2,929
-3 votes
1 answer
811 views

combinatoric proof $\sum_{i=0}^{n}(-1)^i\binom{n}{i}\binom{n-i+k-1}{k}=\binom{k-1}{k-n}$ [closed]

I would like help with combinatorial proof , not algebraic proof . Thank you for your time $\sum_{i=0}^{n}(-1)^i\binom{n}{i}\binom{n-i+k-1}{k}=\binom{k-1}{k-n}$
maya cohen's user avatar
1 vote
0 answers
46 views

Uniformization of triangulation on a sphere up to Moebius transformations

This is not the most precise question but rather a hope that someone has seen something like this. I am given a triangulation of the 2-sphere $S^2$ which I only know up to Moebius transformations. I ...
Bobby Nik's user avatar
3 votes
1 answer
307 views

Planar subsets with many pairs of points on distance $1$ [duplicate]

Let $X$ be a subset of $\mathbb R^2$ consisting of $n$ distinct points. Let $d_1(X)$ be the number of pairs of points of $X$ on distance $1$ from each other. Define $$d_1(n)=\sup_{X\subset \mathbb R^2|...
aglearner's user avatar
  • 14k
6 votes
2 answers
423 views

On planar sections of 3D convex bodies

Consider the space of planar sections of any given convex 3D body. Basic Question: What is the lower bound for the ratio $$\frac{\text{area of section of greatest perimeter}} {\text{area of section of ...
Nandakumar R's user avatar
  • 5,401
4 votes
2 answers
289 views

Which convex pentagon gives least packing density?

Among all convex pentagons, does the regular pentagon give least packing density? Further question: For each $n > 6$, is the regular $n$-gon the minimum of packing density? An analogous question ...
Nandakumar R's user avatar
  • 5,401
1 vote
0 answers
67 views

Facility location and traveling salesman

This question is based on Distributing points evenly on a sphere and Facility location on manifolds The 'dispersal problem' (which can be mapped to packing disks in many cases) places $n$ points in a ...
Nandakumar R's user avatar
  • 5,401
8 votes
1 answer
145 views

The polytope algebras generated by polytopes with rational vs arbitrary vertices

The polytope algebra was defined by P. McMullen in "The polytope algebra" Adv. Math. 78 (1989) as follows. Let us denote by $\Pi'_\mathbb{R}$ the quotient of the free abelian group generated ...
asv's user avatar
  • 21.1k
4 votes
0 answers
111 views

Projective planes over algebraically closed fields

Suppose I am given a projective plane $P \cong \mathbb{P}^2(k)$ over a (commutative) field $k$. With "projective plane," I mean the point-line geometry (and not, for instance, the scheme): $...
THC's user avatar
  • 4,313
1 vote
3 answers
142 views

On packing axisymmetric bodies in 3D

Consider any 3D body with an axis of rotational symmetry (e.g. cone, cylinder...) and packing the 3d space efficiently with infinitely many copies of this body. Is the following claim valid? Claim: ...
Nandakumar R's user avatar
  • 5,401
21 votes
3 answers
895 views

Cutting of a regular polygon into congruent pieces

Question. For which $N$ it is possible to cut a regular $N$-gon into congruent pieces such that the center of the regular polygon lies strictly inside one of the pieces? For $N=3,4$ there are trivial ...
Fedor Nilov's user avatar
4 votes
1 answer
140 views

How many regular d-dimensional simplices of side length 1/2 are required to cover a regular d-dimensional simplex of side length 1?

For positive integers $n$ and $d$ satisfying $d = n-1$, let the $d$-dimensional regular simplex of side-length $\sqrt{2}$ be $X = \{(x_1, x_2, \cdots, x_n) \in \mathbb{R}^n: x_1+x_2+\cdots + x_n = 1, ...
atenao's user avatar
  • 173
0 votes
0 answers
52 views

What do optimal tours tell about finite point sets?

Let $T_{\mathrm{MIN}}$ and $T_{\mathrm{MAX}}$ denote the shortest, resp. longest Hamilton cycle through a set of $n=2k+1$ points. Let further $S_{\mathrm{MIN}}$ and $S_{\mathrm{MAX}}$ be the "...
Manfred Weis's user avatar
  • 12.6k
8 votes
1 answer
311 views

Are there any convex pentagonal rep-tiles?

A rep-tile is a shape that can tile larger copies of the same shape. Question 1: Are there any convex pentagons that are also rep-tiles? Remarks: 15 convex pentagonal tiles of the plane are known and ...
Nandakumar R's user avatar
  • 5,401
15 votes
2 answers
763 views

Three squares in a rectangle

One of my colleagues gave me the following problem about 15 years ago: Given three squares inside a 1 by 2 rectangle, with no two squares overlapping, prove that the sum of side lengths is at most 2. (...
udaque's user avatar
  • 153
1 vote
0 answers
121 views

A center of convex planar regions based on chords

This is based on Chapter 6 of 'Convex figures' by Yaglom and Boltyanskii. This post also continues On two centers of convex regions. A point $P$ in the interior of a planar convex region $C$ divides ...
Nandakumar R's user avatar
  • 5,401
1 vote
0 answers
45 views

Multi-layered wrapping of polyhedra

This post continues from How big a box can you wrap with a given polygon? and Convex polyhedra that can be folded from convex polygons. One can also mention 'k-fold coverings of the plane' as examined ...
Nandakumar R's user avatar
  • 5,401
2 votes
1 answer
108 views

Convex polyhedra that can be folded from convex polygons

This question is based on http://www.science.smith.edu/~jorourke/Papers/FoldingPP.pdf. Therein is stated the theorem: Every convex polygon folds to an infinite number (a continuum) of noncongruent ...
Nandakumar R's user avatar
  • 5,401
2 votes
0 answers
863 views

Happy ending problem – Why not a proof by induction?

I have been thinking for a while on the happy ending problem, looking for approaches to attack the Erdős–Szekeres conjecture: the smallest number of points for which any general position arrangement ...
Juan Moreno's user avatar
6 votes
0 answers
219 views

How big a box can you wrap with a given polygon?

Question: Given a convex polygonal region, how does one find the box (rectangular parallelopiped) of maximum volume that can be wrapped with this region? While wrapping, if needed, some portions of ...
Nandakumar R's user avatar
  • 5,401
3 votes
1 answer
133 views

Covering radius of a lattice from relevant vectors

Let $L$ be an $n-$dimensional lattice. The Voronoi region of $L$ is given by $$ \mathcal{V}(L)=\big\{x\in\mathbb{R}^n~|~ \|x\|_2\leq \|x-v\|_2~\forall v\in L\setminus\{0\}\big\}. $$ Considering the ...
FermaX's user avatar
  • 33

1
6 7
8
9 10
37