Questions tagged [discrete-geometry]

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

Filter by
Sorted by
Tagged with
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
2 votes
1 answer
122 views

On equal area planar sections of 3D convex bodies

This is an extension of On segments of equal area cut from planar convex regions by chords. While the 3D analog of the above question would be about 3D pieces cut from a convex body $C$ by planes, ...
Nandakumar R's user avatar
  • 5,473
2 votes
0 answers
136 views

On segments of equal area cut from planar convex regions by chords

Consider a planar convex region $C$ of unit area and all chords of it that cut off a segment of area $\alpha$ from $C$. Obviously, if $C$ is a circular disk of unit area, all segments of area $\alpha$ ...
Nandakumar R's user avatar
  • 5,473
0 votes
0 answers
20 views

Smallest Semi-ellipses that contain a convex n-gon

Definition: Let us define a semi-ellipse as either of the two halves into which an elliptical region is cut by any line that passes through its center. Obviously, all semi-ellipses that come from any ...
Nandakumar R's user avatar
  • 5,473
2 votes
0 answers
60 views

Degeneracy and the "Linear Degeneracy Testing" problem

The Affine Degeneracy problem is about deciding whether $n$ given points in $\mathbb{R}^d$ (or $\mathbb{Q}^d$) are "in general position". i.e. there is no $d+1$ tuple of points which lies in ...
Tippisum's user avatar
  • 153
0 votes
0 answers
46 views

Optimal packing and covering of a triangle with squares

We continue from Another variant of the Malfatti problem. Given a triangle T and a number n, how to cover it with n squares (of possibly different dimensions) such that the sum of the areas (...
Nandakumar R's user avatar
  • 5,473
16 votes
0 answers
560 views

Snakes on a plane

A sleeping bag for a baby snake in $d$ dimensions (no, really) is a subset of $\mathbb{R}^d$ which can cover (via translation and rotation) every (piecewise-smooth for concreteness) curve of unit ...
Noah Schweber's user avatar
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 ...
an_ordinary_mathematician's user avatar
1 vote
1 answer
62 views

Covering convex regions with disks optimizing on area and perimeter

Question: Are there planar convex regions $R$ and integers $n$ with the property: if $R$ is covered by $n$ disks of possibly different sizes such that (1) the total area of the covering disks is ...
Nandakumar R's user avatar
  • 5,473
2 votes
0 answers
76 views

Another variant of the Malfatti problem

We try to add to A Variant of the Malfatti Problem As stated in the Wikipedia entry on Malfatti circles, it is an open problem to decide, given a number $n$ and any triangle, whether a greedy method ...
Nandakumar R's user avatar
  • 5,473
4 votes
2 answers
189 views

Algorithm for grouping tetrahedra from Voronoi diagram

I have a set of 3D Voronoi generator points and their neighbouring points, which, when connected, should result in a Delaunay tetrahedralization. However, I'm having a hard time implementing this. My ...
catmousedog's user avatar
5 votes
0 answers
71 views

Is the choosability/list chromatic number of a circular arc graph equal to its chromatic number?

In 2003, Prowse and Woodall proved that for graphs $C_n^k$ which are powers of cycles, $$\chi_\ell(C_n^k) = \chi(C_n^k).$$ They conjectured that this equality holds for the broader class of graphs ...
CTVK's user avatar
  • 151
1 vote
0 answers
41 views

Does a substitution tiling being FLC depend on starting seed?

I've been trying to understand more on "geometric" substitutions rather than just symbolic ones. As symbolic substitutions always yield FLC tilings, I wanted to know whether a tiling coming ...
Keen-ameteur's user avatar
1 vote
0 answers
63 views

Detecting points inside the convex hull with inner products

Given a finite set $P$ of $n\gt d+1$ points in $d$-dimensional euclidean space. Under the assumption that the points of $P$ are in general position in the sense that $\lbrace p_{i_1},\dots,p_{i_d}\...
Manfred Weis's user avatar
  • 12.6k
4 votes
1 answer
266 views

Billiard circuits in pentagons

A billiard circuit in a convex $n$-gon is a closed billiard path of $n$ segments reflecting from consecutive edges of the polygon. Every regular $n$-gon has such a billiard circuit: Recently a ...
Joseph O'Rourke's user avatar
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 ...
Keen-ameteur's user avatar
1 vote
0 answers
131 views

A comparison between packing and covering as classes of problems

We continue from Bounds for the Dispersal Problem in convex regions and Bounds for minimax facility location in a convex region Let us consider the classes of problems: Given a convex region $R$ and ...
Nandakumar R's user avatar
  • 5,473
0 votes
0 answers
61 views

Bounds for the Dispersal Problem in convex regions

We add a bit to: Bounds for minimax facility location in a convex region Two earlier posts: Cutting convex regions into equal diameter and equal least width pieces - 2 and Facility location on ...
Nandakumar R's user avatar
  • 5,473
1 vote
0 answers
139 views

Ways of proving that a framework is locally rigid

Given a (bar-and-joint) framework/linkage, I would like to know what are possible ways of showing that the framework is locally rigid. Also, what is known about the computational complexity of ...
Pritam Majumder's user avatar
1 vote
0 answers
85 views

Bounds for minimax facility location in a convex region

An earlier question: Facility location on manifolds A possibly related earlier post: Cutting convex regions into equal diameter and equal least width pieces - 2 The minimax facility location problem ...
Nandakumar R's user avatar
  • 5,473
3 votes
0 answers
136 views

Algorithm to dissect a polygon into a minimum amount of rectangles, conditioned on a maximum overlap

I have the following problem, I have a problem regarding concave polygons. I want to write code to cover any polygon with a minimum amount of rectangles that are allowed to overlap and have no fixed ...
PeterCrouch's user avatar
8 votes
1 answer
419 views

When can $L$ sets of the form $\{a,b,a+b\}$ partition $\{1,2,\dots, 3L\}$?

Firstly, this question has been posted to Math StackExchange with no complete answer so far. Consider a set of the form $\{a,b,a+b\}$ where $a$ and $b$ are positive integers with $b > a$. I will ...
Mohannad Shehadeh's user avatar
2 votes
2 answers
347 views

Sphere tessellation with congruent regular hexagons except finitely many

Let $S^2$ be the 2 dimensional sphere embedded in $\mathbb{R}^3$. It is well known, using the Euler characteristic, that it is not possible to tessellate $S^2$ with all congruent regular hexagons. My ...
maria_c's user avatar
  • 131
8 votes
0 answers
105 views

Is there an inventory of closed billiard paths in a regular tetrahedron?

Conway found a closed billiard-ball trajectory in a regular tetrahedron: Image: Izidor Hafner Since then Bedaride and Rao Bedaride, Nicolas, and Michael Rao. "Regular simplices and periodic ...
Joseph O'Rourke's user avatar
12 votes
0 answers
160 views

Can the optimal packing density in $\mathbb{Z}^d$ be irrational?

For a finite $S \subset \mathbb{Z}^d$, let $d_p(S)$ be its optimal packing density. That is, the maximal lower asymptotic density of $A+S$, where $A \subset \mathbb{Z}^d$ is such that $(a_1+S)\cap (...
Arsenii Sagdeev's user avatar
3 votes
2 answers
188 views

Random walk to visible lattice points

Consider a random walk from the $\mathbb{Z}^2$ origin $(0,0)$ to visible (not blocked) lattice points $p$, with a parameter $r$ a given radius of a circle centered on $p$. With $p$ the previous point, ...
Joseph O'Rourke's user avatar
3 votes
1 answer
353 views

Illumination from visible lattice points with inverse square intensity

It is well known that the number of $\mathbb{Z}^2$ lattice points visible from the origin is $6/\pi^2$, about $61$%. See, e.g., What fraction of the integer lattice can be seen from the origin?. I am ...
Joseph O'Rourke's user avatar
9 votes
2 answers
475 views

Connected geometric thickness two

A graph $G = (V,E)$ has geometric thickness two if there exists an embedding $\varphi: V \rightarrow \mathbb{R}^2$ and a decomposition $E = E_1\cup E_2$ such that $G_1 = (V,E_1)$ and $G_2 = (V,E_2)$ ...
Till's user avatar
  • 469
9 votes
4 answers
410 views

Minimum number of common edges of triangulations

Let $S$ and $T$ be two triangulations. We define $c(S,T)$ as the number of edges shared by $S$ and $T$. With this, we can define $f(n) = \min_{P} \min_{S,T} c(S,T)$. Here the first minimum goes over ...
Till's user avatar
  • 469
4 votes
1 answer
280 views

Does Kalai's $3^d$ conjecture hold for simplicial spheres?

Kalai's $3^d$ conjecture asserts that every centrally symmetric $d$-polytope has at least $3^d$ non-empty faces. This is open in general, but has been proven for simplicial polytopes. Question: Does ...
M. Winter's user avatar
  • 12.5k
3 votes
0 answers
114 views

Divide Euclidean space by surfaces

It is well known that $n$ hyperplanes in $\mathbb{R}^k$ can divide $\mathbb{R}^k$ into at most $p$ regions where $p$ is \begin{equation} 1 + n + C^2_n + \cdots + C^k_n \end{equation} Is there similar ...
Hao Yu's user avatar
  • 185
4 votes
2 answers
157 views

On the number of intersection points between a curve and a (horizontal, vertical) line inside a unit square

I am looking for a reference (name, source) of the following elementary geometric combinatorial problem: Inside a unit square, given a smooth curve of length $L$. Then there exists a horizontal or ...
Vihun Pa's user avatar
0 votes
0 answers
111 views

Frameworks in general position that are locally rigid but not infinitesimally rigid

The classical theorem of Asimow and Roth says that for a generic framework (i.e., coordinates of the nodes are algebraically independent), local rigidity and infinitesimal rigidity are equivalent. I ...
Pritam Majumder's user avatar
2 votes
1 answer
94 views

The problem of finding the smallest number of copies of a certain shape that can be placed into a space to make fitting another copy impossible

Packing problems often ask for the largest number of some identical shape that can fit in a given space without overlapping, if they are placed optimally. I'm interested in the opposite question: Q. ...
EdvinW's user avatar
  • 121
4 votes
0 answers
109 views

Advice on results for balls on regular $N$-dimensional grids

I have obtained some results regarding balls on regular $N$-dimensional grids. I would like expert opinion on wether the results are significant or interesting enough for (trying to) publish them in a ...
Luis Mendo's user avatar
0 votes
0 answers
165 views

Sum of square of parts, and sum of binomials over integer partition

Let $n$ be positive integer. Consider its integer partitions denoting as $(m_1,\cdots,m_k)$, where $m_1+\cdots+m_k=n$ and the order does not matter. We ignore the case of $(m_1,\cdots,m_k)=n$. I am ...
tony's user avatar
  • 297
0 votes
0 answers
41 views

3d convex body with max kissing number with translates

Ref: Convex region $C$ with least kissing number of copies of $C$ Given a convex body $C$, let us define its 'translate kissing number' $k_t$ as the largest possible number of translated copies of $C$ ...
Nandakumar R's user avatar
  • 5,473
1 vote
0 answers
37 views

The optimal embedded and enclosing cardioids for a triangle

Ref: https://en.wikipedia.org/wiki/Cardioid Earlier posts with similar questions: Smallest 3-ellipses that contain triangles and Curves of constant width that contain triangles Questions: Given any ...
Nandakumar R's user avatar
  • 5,473
43 votes
0 answers
1k views

Can a regular icosahedron contain a rational point on each face?

The title says it all: Is there a (regular) icosahedron containing a rational point on each of its faces? For other Platonic solids, the affirmative answer is easy. Indeed, regular tetrahedra, cubes, ...
Ilya Bogdanov's user avatar
3 votes
0 answers
90 views

Minimal set of geometric moves in various equivalence classes of triangulated geometries

I would like to get to know what is the minimal set of geometric changes "aka. moves" (topology preserving modifications / Pachner moves / bistellar moves) that can transform any 3-...
Kregnach's user avatar
0 votes
0 answers
89 views

Which polytopes can be folded to an edge?

While playing with bar-and-joint linkages, I noticed that the skeleton of a regular 3-dimensional cube can be folded to a single edge (this can be achieved by first flexing the cube to bring it to a ...
Pritam Majumder's user avatar
1 vote
0 answers
44 views

Which rectangles can be cut into mutually non-congruent rectangles all of same diagonal length?

This earlier post asks, among other things, whether the plane can be tiled with mutually non-congruent rectangles all of which have same length of diagonal: Tiling the plane with mutually non-...
Nandakumar R's user avatar
  • 5,473
2 votes
0 answers
99 views

Minimum number of points on sphere which cannot be covered by three double caps

What is the minimum number of points on the sphere $S^d \subset \mathbb{R}^{d+1}$ which cannot be covered by $d+1$ double caps? A double cap is defined to be a set $\{x \in S^d: |\langle x,a \rangle| &...
Tommy Williams's user avatar
3 votes
1 answer
100 views

Does a matroid base polytope contain its circumcenter?

Let $(X,\mathcal B)$ be a matroid on the ground set $X=(x_1,...,x_n)$ and with set of bases $\mathcal B$, and let $P\subset\Bbb R^n$ be its matroid base polytope (i.e. the convex hull of the ...
M. Winter's user avatar
  • 12.5k
4 votes
0 answers
78 views

Which rectangles can be cut into finitely many rectangles all with same perimeter and different areas?

Ref 1: dividing a square into unique rectangles with the same perimeter https://arxiv.org/ftp/arxiv/papers/1307/1307.3472.pdf Ref 1 asks if a square can be cut into some finite number of rectangles ...
Nandakumar R's user avatar
  • 5,473
0 votes
0 answers
30 views

Convex 3d bodies for which all planar sections with max diameter have same diameter

Ref: 1. A claim on planar sections of 3D convex bodies On convex 3d bodies whose shadows are all of constant diameter Given a 3D convex body $C$ and a specified direction $n$, we consider the planar ...
Nandakumar R's user avatar
  • 5,473
3 votes
0 answers
89 views

On convex 3d bodies whose shadows are all of constant diameter [closed]

We add a bit to More on shadows of 3D convex bodies By a shadow of a 3D body, we mean the orthogonal projection of it onto a 2D plane. If all shadows of a convex 3D body have the same diameter, will ...
Nandakumar R's user avatar
  • 5,473
10 votes
1 answer
489 views

A projective plane in the Euclidean plane

Problem. Is there a subset $X$ in the Euclidean plane such that $X$ is not contained in a line and for any points $a,b,c,d\in X$ with $a\ne b$ and $c\ne d$, the intersection $X\cap\overline{ab}$ is ...
Taras Banakh's user avatar
  • 40.8k
0 votes
1 answer
48 views

On largest convex m-gons contained in a given convex n-gon where m < n

This post is the inside-out variant of On smallest convex m-gons that contain a given n-gon where m<n Given a convex n-gon region P, and an m less than n, how to find the max area convex m-gon Q ...
Nandakumar R's user avatar
  • 5,473
1 vote
0 answers
121 views

The number of incidences between points and parabolas on $\mathbb{R}^2$

I was reading Adam Sheffer's book "Polynomial Methods and Incidence Theory" and I tried to solve the following exercise: Exercise 1.1 Construct a set $\mathcal{P}$ of $m$ points and a set $\...
RFZ's user avatar
  • 298

1
2
3 4 5
37