All Questions
Tagged with mg.metric-geometry discrete-geometry
671 questions
10
votes
1
answer
623
views
Polyhedron not circumscribed about a sphere
Let $P$ be a polyhedron whose faces are colored black and white so that there are more black faces and no two black faces are adjacent. Show that $P$ is not circumscribed about a sphere.
My teacher ...
- 1,090
6
votes
1
answer
205
views
Hiding $k$ disks inside a larger disk
Suppose one has $k$ unit-radius disks, and the goal is to hide them inside
a disk of radius $R \gg k$.
The detection probes are rays along a line.
(Think of the disks as tumor cells, and the rays as ...
- 151k
5
votes
2
answers
378
views
Light inside a polyhedron
I have two questions the same as Mostafa's Question:
Visibility of vertices in polyhedra
Suppose $P$ is a closed polyhedron in space (i.e. a union of polygons which is homeomorphic to $S^2$) and $X$ ...
- 628
28
votes
5
answers
2k
views
Visibility of vertices in polyhedra
Suppose $P$ is a closed polyhedron in space (i.e. a union of polygons which is homeomorphic to $S^2$) and $X$ is an interior point of $P$. Is it true that $X$ can see at least one vertex of $P$? More ...
- 4,484
9
votes
1
answer
2k
views
Billiard dynamics with angle of reflection a fraction of angle of incidence
Suppose that a billiard ball bouncing in a unit square (or a lightray reflecting
in a mirrored square) has the property that the angle of reflection is a fraction
of the angle of incidence, rather ...
- 151k
3
votes
1
answer
1k
views
Bound on maximum distance between points on a unit N-Sphere
I want to select M points on the N-sphere such that $min_{i\neq j,i,j\in \{1..M\}} ||x_i - x_j||$ is maximized.
Are there good upper bounds for this max-min distance?
- 41
4
votes
1
answer
258
views
The Mahler conjecture and non-zonoidal 3-polytopes (4-polytopes)
I have been working on the Mahler conjecture for over a year now and have made some progress for certain classes of convex polytopes and I'm now attempting to write up my results specified to $\mathbb{...
- 1,441
1
vote
1
answer
57
views
Maximum crossings of curvature-constrained curve
Let $C$ be a curve in the plane whose curvature is everywhere $\le 1$.
If $C$ has length $L$, what is the largest number of proper self-crossings
of $C$ as a function of $L$?
For example, the curve ...
- 151k
3
votes
1
answer
553
views
Calculate the discrete set of points B which are in the convex hull of the set of points A
This problem is likely best described with the following picture:
Given the discrete set of points $A$ (shown in blue), I wish to calculate the discrete set of points that are contained within the ...
- 151
41
votes
2
answers
2k
views
Can we find lattice polyhedra with faces of area 1,2,3,...?
I asked this question two months ago on MSE, where it earned the rare
Tumbleweed badge for garnering zero votes, zero answers, and 25 views over 61 days.
Perhaps justifiably so! Here I repeat it with ...
- 151k
2
votes
0
answers
112
views
What is the projective dual of a planar graph?
Everybody learns the usual definition of the dual of a planar graph when edges are preserved and faces are mapped to vertices. Everybody learns the projective duality. What if we apply it to a ...
- 18.9k
7
votes
1
answer
439
views
Integral straight-line embeddings of planar graphs
Wikipedia says (in the article on Fáry's theorem),
"Heiko Harborth raised the question of whether every planar graph has a straight line representation in which all edge lengths are integers. The ...
- 151k
1
vote
0
answers
80
views
Euclidean embedding of a graph based on 1-ring neighborhood distances only
Consider a graph $(V,E)$, $\vert V \vert = n$ and weights $\{l_{ij}\}$, where $l_{ij}>0$ iff there is an edge connecting vertices $v_i$ and $v_j$. Distances beyond the 1-ring neighborhood are not ...
- 337
2
votes
1
answer
133
views
Omit each vertex in turn of convex polygon: Iterative limit?
Let $P=P_0$ be a convex polygon of $n$ vertices $v_k$.
Let $P_{i+1}$ be the convex polygon obtained by intersecting the halfplanes
determined by the lines through every other vertex.
Below, $P_0$ is ...
- 151k
9
votes
2
answers
3k
views
get a point in polygon (maximize the distance from borders)
I have several 2D polygons represented by lists of xy-coordinates of their vertices.
It is needed to get several points inside the polygon so that they lie possibly far from the polygon's borders (...
0
votes
1
answer
214
views
Generalized Sphere Kissing Problem [duplicate]
I am currently researching discrete geometry and I am in need of an upper bound on a generalized kissing number in 3-dimensions dependent upon a parameter $\eta$ which is the radii of spheres touching ...
- 1,441
15
votes
2
answers
571
views
Spearing rolling hula hoops
Or: Stabbing rolling disks.
Imagine there are $n$ unit-diameter disks rolling between $x=0$ and $x=d$,
reflecting off either end.
The disk centers start at a random location within $[\frac{1}{2}, d-\...
- 151k
7
votes
2
answers
453
views
Bound on Minimal Length of Vectors in Lattice and its Dual Lattice
Let $\Lambda$ be a lattice in $\mathbb{R}^n$ and $\Lambda^\ast$ its dual lattice. Let $d=\min_{v\in\Lambda} (v,v)$ and $d^\ast =\min_{v\in\Lambda^\ast} (v,v)$ be the minimal squared lengths of vectors ...
- 679
11
votes
2
answers
444
views
The intersection of a circle and a rank 3 subgroup of the plane
Let $A$ be a rank 3 subgroup of the Euclidean plane, i.e. $A = \mathbb{Z} v_1 + \mathbb{Z} v_2 + \mathbb{Z} v_3$, where $v_1, v_2, v_3 \in \mathbb{R}^2$ are three $\mathbb{Q}$-linearly independent ...
- 1,531
5
votes
1
answer
406
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 ...
- 867
5
votes
4
answers
540
views
How hard is it to determine if a weighted graph can be isometrically embedded in R^3?
Consider a graph $G$ with nonnegative edge weights.
Question: In $\mathbb{R}^3$, how hard is it to assign coordinates to vertices such that the Euclidean length of each edge is equal to its weight?
...
- 3,059
65
votes
3
answers
3k
views
How many unit cylinders can touch a unit ball?
What is the maximum number $k$ of unit radius, infinitely long cylinders with mutually disjoint interiors that can touch a unit ball?
By a cylinder I mean a set congruent to the Cartesian product of ...
- 7,276
0
votes
0
answers
143
views
On 'Very Movable' Geometric Configurations (Configurations with a large degree of freedom)
Let $C$ be an $(n_r, b_k)$ combinatorial configuration that admits a geometric realization in the plane. I'm interested in the maximum number of points/lines $M$ of $C$ we can place in general ...
- 93
24
votes
3
answers
3k
views
Can a unit square be cut into rectangles that tile a rectangle with irrational sides?
For arbitrary positive integers $m$ and $n$, if we dissect a unit square into an $m\times n$ rectangular grid of $1/m\times 1/n$ rectangles, we can reassemble these $mn$ rectangles into an $n/m\times ...
- 2,437
3
votes
0
answers
135
views
Lattices achieving best density
Let $\Lambda \subset \mathbb{R}^n$ be an Euclidean lattice with generator matrix $B$. Define the center density $\delta(\Lambda)$ in the usual way as $\delta(\Lambda) = \rho^n/|\det{B}|$, where $\rho$ ...
- 800
16
votes
3
answers
2k
views
Are infinite planar graphs still 4-colorable?
Imagine you have a finite number of "sites" $S$ in the positive quadrant
of the integer lattice $\mathbb{Z}^2$,
and from each site $s \in S$, one connects $s$ to every lattice point to which it
has a ...
- 151k
49
votes
4
answers
4k
views
What fraction of the integer lattice can be seen from the origin?
Consider the integer lattice points in the positive quadrant $Q$ of $\mathbb{Z}^2$.
Say that a point $(x,y)$ of $Q$ is visible from the origin if the
segment from $(0,0)$ to $(x,y) \in Q$ passes ...
- 151k
5
votes
1
answer
532
views
Regular lattice polygons
Suppose I want to construct an $N$-gon in the plane whose vertices are integer lattice points, and which is close to a regular $N$-gon (which means, the ratio of longest to the shortest side is within ...
- 96.4k
1
vote
0
answers
60
views
Finding special vectors generated by a matrix
Let $G\in \Bbb Z^{n\times n}$ be a unimodular matrix.
Are there any efficient algorithms to find the maximum norm of a vector $v$ that satisfies $\langle\Delta(v),v\rangle=0$ over all vectors $v\in ...
- 13.9k
14
votes
0
answers
479
views
Does every convex polyhedron have a combinatorially isomorphic counterpart whose angles between edges are rational multiples of $\pi$?
After reading these very interesting questions, I came up with another one:
Does every convex polyhedron have a combinatorially isomorphic counterpart whose angles between all pairs of edges meeting ...
- 532
6
votes
0
answers
114
views
Constructing a polyhedron of maximal possible volume from given bounds on areas of its faces
Consider $n$ variables $a_1,...,a_n$ ranging over $\mathbb{R}^+$. Suppose we are given $n$ pairs of positive rational numbers $(p_1,q_1),...,(p_n,q_n)$ where each pair imposes bounds on the ...
- 161
2
votes
1
answer
1k
views
Geodesic convex hulls in a graph; and their properties
This question asks for an analog of the convex hull in a graph that parallels
(as far as possible) convex sets in Euclidean space.
Let $G$ be a simple, undirected graph, and let $S \subseteq V$ be a ...
- 151k
16
votes
0
answers
298
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 ...
- 31.2k
51
votes
3
answers
3k
views
Can the sphere be partitioned into small congruent cells?
On the unit $2$-sphere ${\mathbb S}^2$ furnished with the geodesic distance, a subset homeomorphic to a planar disk is called a cell. A finite family of cells is a tiling if their interiors are ...
- 7,276
20
votes
1
answer
452
views
Hidden points in polygons
Let $h(n)$ be the largest number of mutually invisible points that can be located in a
polygon $P$ of $n$ vertices. Two points $x$ and $y$ are mutually invisible if the segment
$xy$ contains a point ...
- 151k
3
votes
1
answer
518
views
n-dimensional Delaunay Triangulation of Lattices
I have several questions concerning the Delaunay triangulation of a high dimensional lattice.
Given an $n$-dimensional lattice $L$ and its Delaunay triangulation (partition of $R^n$ into simplices ...
- 31
24
votes
3
answers
1k
views
Tetrahedron insphere iteration
I know that iterating the following incircle construction approaches an equilateral triangle in the limit:
Starting with any triangle $T$, one forms $T'$ by connecting ...
- 151k
4
votes
2
answers
1k
views
Sphere - Symmetry and Triangulation [closed]
The sphere is symmetric with respect to any rotation. However, it loses this property as soon as it is triangulated. Are there sequences of triangulations that possess particular large symmetry groups ...
- 1,256
0
votes
1
answer
73
views
Optimal radiating $(d{-}1)$-flats within a sphere
Permit me to revisit an earlier unresolved MO question,
"Chord arrangement that avoids confining small or large disks"
with a (very!) specific version, inspired by radiation therapy.
The main idea is ...
- 151k
7
votes
2
answers
907
views
Is there a 3d equivalent of this picture?
This question arises apropos of an earlier question I asked that was (VERY!!!) helpfully answered by Anton Petrunin:
Fitting a mesh to a density function
The picture below is the image of a regular ...
- 1,125
8
votes
2
answers
2k
views
Embedding points in 2D based on distance estimates?
Suppose we have a collection of exactly $N$ points (say $N=1000$), with each point belonging to 2-dimensional Euclidean space $\mathbb{R}^2$, but we don't know the coordinates of the points. Suppose ...
- 4,229
3
votes
1
answer
156
views
Points in general position on a small grid
A point set $P$ is said to be embedded in $\mathbf{Z}^2$ in general position, if no three points lie on a common line. Assume that $|P|=n$, I am interested in the smallest $k \times k$ integer grid in ...
- 133
9
votes
1
answer
370
views
Largest convex hull of a unit length path
What is the largest area possible for the convex hull of a path of unit length lying on a plane? For what paths is that largest area attained?
- 851
14
votes
2
answers
878
views
Sets of evenly distributed points in the Euclidean plane
Is there a set $P \subset \mathbb{R}^2$ of points in the Euclidean plane whose intersection
with every convex subset of $\mathbb{R}^2$ of area $1$ is nonempty but finite?
If the answer is yes, can $P$...
- 19.6k
7
votes
1
answer
292
views
Can a tangle of arcs interlock in plane?
This is a variation of the question Can a tangle of arcs interlock?, asked by Joseph O'Rourke, and solved. I reproduce the question here:
Can a (finite) collection of disjoint circle arcs in $\...
- 4,312
4
votes
1
answer
333
views
n-simplex in an intersection of n balls
Consider any $n$-simplex, $n \geq 2$. For each edge $(i,j)$, consider $n$-ball $B_{ij}$ such that vertices $x_i$ and $x_j$ are antipodal on this ball. Fix a point $x_0$ in the simplex. The question: ...
- 195
2
votes
0
answers
586
views
Partitioning the Projective Plane
Throughout this post, by projective plane I mean the set of all lines through the origin in $\mathbb{R}^3$.
Side Note: If there are more standard definitions for any of the ideas presented here, ...
- 761
2
votes
2
answers
284
views
Three questions concerning lattice points on sphere surfaces
Pardon my ignorance of this topic.
Q1.
In which dimensions $d$ is it the case that, for every natural number $n$,
there exists a sphere having exactly $n$ lattice points on it $(d{-}1)$-...
- 151k