All Questions
984 questions
66
votes
3
answers
4k
views
Reasons to prefer one large prime over another to approximate characteristic zero
Background:
In running algebraic geometry computations using software such as Macaulay2, it is often easier and faster to work over $\mathbb F_p = \mathbb Z / p\mathbb Z$ for a large prime $p$, rather ...
- 7,328
35
votes
4
answers
5k
views
Why are optimization problems often called "programs"?
Why are optimization problems often called programs?
linear programming
geometric programming
convex programming
Integer programming
...
- 461
32
votes
4
answers
7k
views
Computational software in Algebraic Topology?
I was wondering if there is any good software out there that allows you to do specific computations in algebraic topology. For example:
Create a simplicial complex/set and ask questions about its ...
- 435
29
votes
6
answers
8k
views
How to find a closest integer point to the intersection of two lines?
Here's a question that originates from StackOverflow.
Given are two lines on a plane, specified by equations ($a x + b y = c$) with integer coefficients. The lines aren't parallel and they don't ...
- 391
27
votes
5
answers
2k
views
Is the matrix $\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}$ nonsingular?
Suppose we have a $(2m-1) \times (2m-1)$ matrix defined as follows:
$$\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}.$$
For example, if $m=3$, the matrix is
$$\begin{pmatrix}6 & 20 & 6& 0 ...
- 1,121
27
votes
3
answers
4k
views
Can squares of side 1/2, 1/3, 1/4, … be packed into three quarters of a unit square?
My question is prompted by this illustration from Eugenia Cheng’s book Beyond Infinity, where it appears in reference to the Basel problem.
Is it known whether the infinite set of squares of side $\...
- 2,896
26
votes
2
answers
4k
views
Why did Robertson and Seymour call their breakthrough result a "red herring"?
One of the major results in graph theory is the graph structure theorem from Robertson and Seymour
https://en.wikipedia.org/wiki/Graph_structure_theorem. It gives a deep and fundamental connection ...
- 290
26
votes
0
answers
907
views
Where to submit this work with several unusual features?
I appreciate that questions about where to submit are generally considered off-topic, but I hope that the unusual features of the present case may make it acceptable.
I have put a monograph on github ...
- 56.9k
25
votes
2
answers
2k
views
An Interesting Optimization Problem
You are given n non-negative integers $a_1, a_2 ,, a_n$. In a single operation, you take any two integers out of these integers and replace them with a new integer having value equal to difference ...
- 363
25
votes
3
answers
2k
views
Is the Ford-Fulkerson algorithm a tropical rational function?
The Ford-Fulkerson algorithm
Let me recall the standard scenario of flow optimization (for integer flows at least):
Let $\mathbb{N} = \left\{0,1,2,\ldots\right\}$. Consider a digraph $D$ with vertex ...
- 33.8k
22
votes
2
answers
3k
views
Missing document request
I received a request for another long-lost document:
I am wondering if there is any way I
might obtain a copy of
The geometry of circles: Voronoi
diagrams, Moebius transformations,
...
- 25.1k
21
votes
8
answers
4k
views
Determine if circle is covered by some set of other circles
Suppose you have a set of circles $\mathcal{C} = \{ C_1, \ldots, C_n \}$ each with a fixed radius $r$ but varying centre coordinates. Next, you are given a new circle $C_{n+1}$ with the same radius $r$...
- 311
20
votes
2
answers
25k
views
Partitioning a polygon into convex parts
I'm looking for an algorithm to partition any simple closed polygon into convex sub-polygons--preferably as few as possible.
I know almost nothing about this subject, so I've been searching on Google ...
- 201
19
votes
4
answers
1k
views
Applications of linear programming duality in combinatorics
So, I know that one can apply the strong LP duality theorem to specific instances of maximum flow problems to recover some nontrivial theorems in combinatorics, such as Hall's theorem, Koenig's ...
- 997
19
votes
2
answers
2k
views
Is the tensor product of polyhedra a polyhedron?
Conventions: A polytope in a finite-dimensional $\mathbb R$-vector space $V$ is defined to be a convex hull of finitely many points in $V$. A polyhedron in a finite-dimensional $\mathbb R$-vector ...
- 33.8k
18
votes
3
answers
3k
views
Deciding membership in a convex hull
Given points $u, v_1, \dots,v_n \in \mathbb{R}^m$, decide if $u$ is contained in the convex hull of $v_1, \dots, v_n$.
This can be done efficiently by linear programming (time polynomial in $n,m$) in ...
- 667
18
votes
1
answer
2k
views
What can be said about the Shadow hull and the Sight hull?
This is a question implicitly raised by Is the sphere the only surface all of whose projections are circles? Or: Can we deduce a spherical Earth by observing that its shadows on the Moon are always ...
- 25.1k
17
votes
3
answers
6k
views
The cone of positive semidefinite matrices is self-dual? (reference needed)
I'm seeking a reference for the following fact.
The cone of positive semidefinite matrices is self-dual (a.k.a. self-polar).
This result is relatively easy to prove, has been known for a long time,...
- 1,513
17
votes
3
answers
2k
views
The minimum of a sum of absolute values of inner products in $\mathbb{R}^d$
Consider a collection of unit vectors $v_1, \ldots, v_n$ in $\mathbb{R}^d$ (we think of $n$ being much larger than $d$). I would like to minimize the sum:
$$\sum_{i\neq j}|\langle v_i,v_j\rangle|.$$
...
- 2,288
17
votes
1
answer
2k
views
How to efficiently vacuum the house
Let $P$ be a polygon (perhaps with no acute angles inside) and let $L$ be a line segment. The segment may move through the area inside $P$ in straight lines, orthogonal to $L$, or it may pivot on any ...
17
votes
2
answers
2k
views
Efficiently determine if convex hull contains the unit ball
Given a set of $n$ points in $\mathbb{R}^d$, is there an algorithm to determine if the convex hull contains the unit ball centered at the origin in polynomial time (in both $n$ and $d$)? The convex ...
- 3,377
17
votes
1
answer
874
views
An NP-hard $n$ fold integral
We are given rational numbers $[c_1, c_2, \ldots, c_n]$ and $v$ from the interval $[0,1]$.
Consider the $n$-fold integral
$$
J = \int_{\theta_1 \in I_1, \theta_2 \in I_2 \ldots, \theta_n \in I_n} d\...
- 627
17
votes
1
answer
580
views
Aperiodic monotile in $\mathbb{R}$
Motivation. Recently a group of researchers found an aperiodic monotile in $\mathbb{R}^2$, answering a long-standing question. There are many results in higher dimensions, so let's explore the lower ...
- 48.8k
16
votes
3
answers
1k
views
Can a convex polytope with $f$ facets have more than $f$ facets when projected into $\mathbb{R}^2$?
Let $P$ be a convex polytope in $\mathbb{R}^d$ with $n$ vertices and $f$ facets.
Let $\text{Proj}(P)$ denote the projection of $P$ into $\mathbb{R}^2$.
Can $\text{Proj}(P)$ have more than $f$ facets?
...
- 163
16
votes
2
answers
5k
views
Weighted area of a Voronoi cell
Let $X = \{ x_1,\dots,x_n\} $ denote a set of $n$ points in the unit square $S = [0,1]\times[0,1]$, and let $w = \{w_1,\dots,w_n\}$ denote a set of weights corresponding to the $n$ points in $X$. ...
- 195
16
votes
3
answers
652
views
How to plot this fractal
I'm a graphic designer and my client has asked me to use this fractal in a design that I'm working on. As you can see, it's not a very good copy, so I'm trying to see if I can generate a high-...
- 263
16
votes
2
answers
277
views
Finding a plane numerically
Suppose I have three large finite sets $\{x_i\}$, $\{y_i\}$ and $\{z_i\}$;
they are obtained by measuring coordinates of a collection of vectors in $\mathbb{R}^3$, but I do not know which triples ...
- 45k
15
votes
3
answers
9k
views
$n$-dimensional Voronoi diagram
I need to compute the Voronoi diagram of a set of points in $R^n$.
I'm quite unschooled on the topic, could someone point me to the right references so that I can
a) understand the theory behind it;
b)...
- 253
15
votes
1
answer
616
views
Acute triangles in "obtuse" polygons?
Let $P$ be a convex polygon. Suppose every interior angle of $P$ is obtuse. Is it always the case that there exist three vertices $p, q, r$ of $P$ such that $\triangle pqr$ is acute?
I conjecture ...
- 173
15
votes
2
answers
3k
views
Given the vertices of a convex polytope, how can we construct its half-space representation?
Let us say I have the vertices of a polytope $V = \{v_1,\dots,v_k\} \subset \mathbb R^n$. Is it possible to write $V$ as intersection of half-spaces using the information from the vertices, i.e., can ...
- 173
15
votes
1
answer
358
views
Are hyperbolic $n$-manifolds recursively enumerable?
Fixing a dimension $n \ge 4$, is the class of closed hyperbolic $n$-manifolds recursively enumerable?
Since hyperbolic manifolds are triangulable I can reformulate this in the following more explicit ...
- 3,399
14
votes
2
answers
540
views
Are all well behaved "mean" functions on $\mathbb{R}^+$ equivalent?
Given a set $S$, a function $M: S\times S \rightarrow S$ is a mean if it satisfies the properties:
$M(a,a)=a\qquad$ (identity)
$M(a,b)=M(b,a)\qquad$ (commutativity).
and possibly
$M(M(a,b),M(a,c))=...
- 5,103
14
votes
2
answers
1k
views
Subfields of a function field
Is there an algorithm for generating (some or all) subfields of a certain genus of a given function field (even a random one,I mean for example generating a random elliptic subfield of a certain given ...
- 601
14
votes
2
answers
635
views
Tarski-Seidenberg for strict inequalities and bounded quantification
This theorem says that quantifiers over real variables can be eliminated from classical first order formulae built from equations and inequalities between polynomials with rational coefficients, ie in ...
- 8,481
14
votes
0
answers
261
views
Dividing a convex region to minimize average distances
Let $C$ be a convex region in the plane with area 1 that contains distinct points $p_1,\dots,p_n$. Say I'd like to divide $C$ into $n$ pieces $C_1,\dots,C_n$, each of area $1/n$, and I'd like to ...
- 4,049
14
votes
0
answers
4k
views
Minimum tiling of a rectangle by squares
Given the $n\times m$ rectangle, I want to compute the minimum number of integer-sided squares needed to tile it (possibly of different sizes).
Is there an efficient way to calculate this?
- 1,015
13
votes
3
answers
1k
views
(non-)existence of the aperiodic monotile
The aperiodic monotile problem asks whether there exists a single tile that every tiling of the plane made with it results non-periodic. What is known about this problem? If this tile exists, how can ...
- 561
13
votes
2
answers
664
views
Complexity of a weirdo two-dimensional sorting problem
Please forgive me if this is easy for some reason.
Suppose given $S$, a set of $n^2$ points in $\mathbb{R}^2$.
I want to choose a bijective map $f$ from $S$ to the set of lattice points in $\lbrace ...
- 19.2k
13
votes
3
answers
834
views
Famous theorems that are special cases of linear programming (or convex) duality
The max flow-min cut theorem is one of the most famous theorems of discrete optimization, although it is very straightforward to prove using duality theory from linear programming. Are there any ...
12
votes
3
answers
1k
views
Is every graph an edge-crossing graph?
Consider a circular drawing of a simple (in particular, loopless) graph $G$ in which edges are drawn as straight lines inside the circle. The crossing graph for such a drawing is the simple graph ...
- 195
12
votes
1
answer
5k
views
Closest 3D rotation matrix in the Frobenius norm sense
Given a 3 by 3 matrix $M$ I would like to find the rotation matrix $R$ minimizing the Frobenius norm:
\begin{equation}
\|R-M\|_F
\end{equation}
Is there a closed form solution for $R$, or is it ...
- 561
12
votes
3
answers
801
views
finding the most-isolated point in a high-dimensional cube
I have a set of points {$x_1,\ldots,x_n$} located in the d-dimensional unit cube $[0,1]^d$. $n$ is about 1000 and $d$ is about 25. I'd like to find
$\max_{\omega\in [0,1]^d}\min_{i=1,\ldots,n} \|\...
- 500
12
votes
1
answer
382
views
Characteristic polynomial of an $8 \times 8$ symmetric matrix with indeterminate entries related to octonionic multiplication
I consider $1,i,j,k,l,m,n,o$ the standard basis of the (complexified if you like) octonions ($\mathbb{O}$ for the octonions).
Let $a = x_1.1 +\ldots + x_8.o$, $b = x_9.1+ \ldots + x_{16}.o$ and $c = ...
- 7,300
12
votes
2
answers
11k
views
Covering a polygon with rectangles
I am trying to cover a simple concave polygon with a minimum rectangles. My rectangles can be any length, but they have maximum widths, and the polygon will never have an acute angle.
I thought about ...
12
votes
1
answer
2k
views
Ways to show a system of polynomial equations has no solution
I came across the following system of polynomial equations on $X_1,\dots,X_{m-2}$:
$$
\begin{cases}
2X_{2s}+\sum\limits_{t=1}^{2s-1}(-1)^tX_tX_{2s-t}=0,\quad s=1,\dots,\frac{m}{2}-1,\\
X_sX_{m-s}+(-1)^...
- 767
11
votes
5
answers
1k
views
Segments of Voronoi Diagrams on smooth manifolds. Are they geodesics?
Let $S$ be a patch of a smooth 2-manifold in $\mathbb{R}^3$, and pick two distinct points $a,\ b \in S$. Let $c$ be the set of points on $S$ equidistant to $a$ and $b$, where distance is defined by ...
- 273
11
votes
2
answers
962
views
Why is modular forms applicable to packing density bounds from linear programming at $n\in\{8,24\}$?
Sphere packing problem in $\mathbb R^n$ asks for the densest arrangement of non-overlapping spheres within $\mathbb R^n$. It is now know that the problem is solved at $n=8$ and $n=24$ using modular ...
- 1,826
11
votes
3
answers
6k
views
Random Sampling a linearly constrained region in n-dimensions...
Hi,
So here is my problem:
Given a nonlinear, discontinous, cost function $f(x_1,x_2,..,x_N)$ along with linear constraints $x_n \ge 0, \forall n$
$x_n \le c_n$
and $\sum_{n=1}^N x_n = 1$ find an ...
- 113
11
votes
2
answers
824
views
A quadratic $O(N)$ invariant equation for 4-index tensors
Consider an $O(N)$ invariant quadratic equation
$$
T_{ijkl}= T_{ijmn}T_{klmn}+ T_{ikmn}T_{jlmn}+ T_{ilmn}T_{jkmn},
$$
where $T_{ijkl}$ is a real, totally symmetric 4-tensor, and the indices run from 1 ...
- 679
11
votes
2
answers
3k
views
Algorithm for embedding a graph with metric constraints
Suppose I have a graph $G$ with vertex set $V$, edge set $E \subseteq {V \choose 2}$, a poistive integer $d$, and a weight function $w:E \to \mathbb{R}^{+}$. Is there a nice algorithmic way to decide ...
- 7,857