Tagged Questions

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

learn more… | top users | synonyms

7
votes
2answers
342 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 ...
6
votes
0answers
165 views

Linked circles in R3

Two circles in 3-D are linked iff each one passes through the interior of the other. There are $N$ points in 3-D in general position (no four lie on a plane). Each triple of points defines a unique ...
3
votes
1answer
552 views

The Stock Market Polytope: Explanation?

Ovidiu Racorean. "Crossing Stocks and the Positive Grassmannian I: The Geometry behind Stock Market." (arXiv Abstract link) Anyone care to offer a summary of what's going on here? (The ...
14
votes
2answers
470 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}, ...
1
vote
1answer
353 views

Study of convex polytopes via commutative algebra

Let $P \subset \mathbb{R}^d$ be any convex polytope with integral vertices, and let $M$ be the additive submonoid of $\mathbb{R}^{d+1}$ which is generated by $\{ (v,1) : v \in P \cap \mathbb{Z}^d \}$. ...
18
votes
2answers
369 views

Trapping a convex body by a finite set of points

In $\mathbb{R}^n$, let $K$ be a convex body and $T$ a finite set of points disjoint from the interior of $K$. Say that $T$ traps $K$ if there is no continuous motion of $K$ carrying $K$ arbitrarily ...
5
votes
2answers
201 views

Genus of Tutte-Coxeter Graph

What is the genus of the Tutte-Coxeter graph -- the incidence graph of the GQ of order 2? Seems like it should be well known, since nearly every other parameter for that graph is known, but I can ...
2
votes
1answer
55 views

Integer point in a non-empty polytope

I have a high-dimensional, non-empty polytope $Ax\geq b$ sitting inside the cube ($0\leq x_i \leq 1$). Is there any general theory or technique to show that this polytope contains an integer point, ...
14
votes
2answers
767 views

Randomly walking a leashed dog

Let a human $h(t)$ random walk on $\mathbb{Z}^2$ by taking a unit-length step at every time step $t$. A dog $d(t)$ on a leash of length $\lambda$ follows $h(t)$, also taking a unit-length step at ...
4
votes
2answers
109 views

The maximal discrete parallelepiped in a convex body

Does the positive constant $c_d$, depending only from dimension, with the following property exist? Property: for every convex body $K\subset \mathbb R^d$ there exists parallelepiped $P\subset K$ ...
11
votes
1answer
293 views

Wander distance of self-avoiding walk that backs out of culs-de-sac

Suppose a self-avoiding walk on $\mathbb{Z}^2$, with random steps each one unit long, backs out of culs-de-sac, but retaining the lattice points on which it stepped marked as unavailable for future ...
4
votes
2answers
156 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 ...
3
votes
1answer
131 views

Partition All $n$-bit Binaries into $n$ Parts

For what values of $n$, it is possible to partition $\mathbb{Z}_2^n$ into $n$ disjoint parts, say $A_1, ..., A_n$ such that every element in $\mathbb{Z}_2^n$ is at most one-edit away from each part, ...
9
votes
2answers
452 views

Finite field Szemeredi-Trotter theorem with unequal number of points and lines

My question concerns the Szemerédi-Trotter theorem in $\mathbb{F}_q^2$. If we have $m$ points and $n$ lines in $\mathbb{F}_q^2$, then by Cauchy-Schwartz the number of point-line incidences is as most ...
9
votes
3answers
344 views

Conjecture on NP-completeness of tesselation of Wang Tile up to finite size

Motivated by these following questions on tessellation: coloring in lattice Reference for Wang Tile Computational approach deciding whether a set of Wang Tile could tile the space up to some size ...
11
votes
2answers
327 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 ...
3
votes
1answer
209 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 ...
5
votes
3answers
279 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? ...
42
votes
2answers
1k views

How many unit cylinders can touch a unit ball?

What is the maximum number $k$ of unit-radius cylinders with mutually disjoint interiors that can touch a unit ball? By a cylinder I mean a set congruent to the Cartesian product of a line and a ...
32
votes
0answers
478 views

Extending a line-arrangement so that the bounded components of its complement are triangles

Given a finite collection of lines $L_1,\dots,L_m$ in ${\bf{R}}^2$, let $R_1,\dots,R_n$ be the connected components of ${\bf{R}}^2 \setminus (L_1 \cup \dots \cup L_m)$, and say that {$L_1,\dots,L_m$} ...
22
votes
3answers
2k 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 ...
3
votes
0answers
89 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$ ...
4
votes
1answer
102 views

Local rigidity of square disk packing

Is the packing of the plane by disks of radius 1/2 centered at the points of ${\bf Z} \times {\bf Z}$ "locally rigid" in the sense that no finite subcollection of the disks admits any joint ...
13
votes
3answers
664 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 ...
35
votes
3answers
1k 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 ...
1
vote
0answers
52 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 ...
3
votes
1answer
295 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 ...
4
votes
0answers
222 views

Unique Domino Tiling

Question: how does one enumerate all star-convex $2n$-vertex sublattices of the plane that have the unique domino-tiling property? Definitions: A subset S of the xy-plane is star-convex if there is ...
6
votes
1answer
418 views

Higher dimensional Rubik's cube group

Since "cubes" with higher dimension than three exist I think it's natural to ask for higher dimensional Rubik's cubes. These so called hypercubes don't seem to have been described from a group ...
28
votes
1answer
542 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 ...
19
votes
1answer
260 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 ...
3
votes
0answers
121 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 ...
1
vote
2answers
236 views

Discrete Laplace operator and its eigenvalues

I wonder is there any geometric interpretation of the eigenvalues ​​of the discrete Laplace operator on graphs? Maybe there is a relationship between the eigenvalues ​​and combinatorial properties of ...
22
votes
3answers
697 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 ...
0
votes
1answer
55 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 ...
5
votes
2answers
453 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 ...
5
votes
2answers
187 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 ...
1
vote
0answers
74 views

Group actions on polytopes in indefinite integer lattices

Is anything at all known about polytopes in indefinite integer lattices? I'm interested in lattice automorphisms which preserve certain polytopes of "high regularity" (e.g. cones). As a first step, ...
3
votes
1answer
72 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 ...
19
votes
2answers
776 views

Erdős, Harary, Tutte's “dimension of graph”: Progress in last 48 yrs?

I just ran across this delightful paper by an amazing triumvirate: Paul Erdős, Frank Harary, and William Tutte. "On the dimension of a graph." Mathematika 12.118-122 (1965): 20. (Cambridge link) ...
12
votes
2answers
445 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 ...
7
votes
1answer
169 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
votes
1answer
196 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: ...
2
votes
0answers
324 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, ...
2
votes
2answers
167 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 ...
1
vote
1answer
189 views

Request for some references exploring the connections of Riemann surfaces with medical imaging

I'd like to know some references for a beginner who has basic background in Riemann surfaces and differential geometry, and would like to start learning/working on more applied areas, medical ...
4
votes
1answer
166 views

Cover of a n-simplex with balls

Consider a n-simplex. For each edge (i,j), consider a n-ball, such that vertices i and j are antipodal on this ball. Is the simplex covered by the union of these balls? Thank you.
17
votes
4answers
745 views

Non-chaotic bouncing-ball curves

I was surprised to learn from two Mathematica Demos by Enrique Zeleny that an elastic ball bouncing in a V or in a sinusoidal channel exhibits choatic behavior:     (The Poincaré map ...
13
votes
1answer
202 views

Smallest regular simplex containing the unit cube in $R^n$

What is the length $e_n$ of the edge of the smallest $n$-dimensional regular simplex $S_n$ containing the $n$-dimensional unit cube $Q_n$? In particular, is there $n$ such that ...
12
votes
7answers
475 views

Can a tangle of arcs of ellipses interlock

This is a variation on an earlier question resolved by user35353: Can a tangle of arcs interlock? In that question, the arcs were restricted to circular arcs, and user35353's proof that one arc can be ...