All Questions
984 questions
4
votes
2
answers
335
views
Software for finding conjugates in the braid group
The conjugacy problem for the braid group was solved by Garside, and gives an algorithm for determining whether two braids are conjugate. Since this algorithm is rather tedious, I was wondering if ...
- 469
1
vote
1
answer
169
views
Best projection on non-convex discrete set with two constraints
I want to compute the projection of a vector $\left( x\right) _{1\leq
i,j\leq n}\in \lbrack 0,1]^{n\times n}$ on the following discrete set
$$
S=\left\{ x\in \{0,1\}^{n\times n}:x_{i,j}+x_{j,i}\leq 1;\...
- 47
1
vote
1
answer
175
views
A variation on the projective Nullstellensatz
Let $V$ be a $\mathbb{C}$-vector space, and let $f_1,\dots,f_n \in S^d(V^*)$ be homogeneous polynomials of degree $d$ for which $V(f_1,\dots, f_n)=\{0\}$.
Must there exist a positive integer $k\geq d$ ...
- 980
11
votes
2
answers
963
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
1
vote
0
answers
96
views
On optimizing a multivariate quadratic function subject to certain conditions
The problem is to maximize $f(x_1,x_2,\cdots,x_n)=\sum\limits_{i=1}^{n}\Big(x_i-k_i\Big)^2$ for $n\ge 3$ subject to the conditions (1) $\sum\limits_{i=1}^{n}x_i=\sum\limits_{i=1}^{n}k_i\le n(n-1)$ ...
- 61
2
votes
1
answer
92
views
Determining if a polygon is convex using relations on orientation of each ordered triple of points
I am reading a paper by Szekeres and Peters on computing the 17-point case of the Erdős–Szekeres conjecture. The conjecture states that the minimum number of points in the plane (in general position, ...
- 123
3
votes
2
answers
157
views
Finding a point inside a surface
I have a triangulation of a surface without boundary in $\mathbb{R}^3$.
The triangulation gives a unit normal pointing outwards for each triangle. I need to find some point in the interior of the ...
- 33
0
votes
0
answers
94
views
Boolean operation on n dimensional polyhedron
A polyhedron in $R^n$ is defined by a set of half-planes: $P = \{x \in R^n \mid Ax - b \le 0\}$.
Given a set of polyhedra in $R^n$, $ P_1, P_2, \dotsc, P_k$, is there an algorithm/implementation that ...
- 21
2
votes
0
answers
119
views
Ellipse of least perimeter that contains a given triangle
This post is related to Smallest 3-ellipses that contain triangles and tries to clarify a basic issue.
Question: Given a general triangle T, How does one find and characterize the ellipse of least ...
- 5,979
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
0
votes
1
answer
36
views
Benefit of adding a trivial constraint to ILPs
let ILP be an integer linear program with constraints-matrix $\boldsymbol{\mathrm{M}}\in\mathbb{Z}^{m\times n}$ and cost vector $\boldsymbol{\mathrm{c}}\in\mathbb{Z}^n$,
${\boldsymbol{\mathrm{x}}^*}\...
- 13.2k
1
vote
0
answers
76
views
Translate of a geodesic that goes through a fixed point on $\mathbb{H}$
Consider the complex upper half plane $\mathbb{H}$ with the hyperbolic geometry. Fix a point $z \in \mathbb{H}$ and also a geodesic $c$. I want to find a hyperbolic translation $\gamma c$ passes that ...
- 577
5
votes
2
answers
241
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 ...
- 5,979
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
1
vote
1
answer
149
views
Existence of element $(x_0,y)$ in a set of common zeros for all $(x_0,y)$ satisfying system of inequalities
Let $f_1,f_2,\cdots,f_n,g_1,g_2\cdots,g_m\in \mathbb{R}[x,y]$, then define the affine variety and semi-affine variety as follows:
$V(f_1,f_2,\cdots,f_n):=\{(x,y)\in\mathbb{C}^2: f_1(x,y)=f_2(x,y)=\...
- 1,875
3
votes
0
answers
285
views
Explicit computations of finite covers of genus one curves with two points of ramification
I have an explicit genus one curve $E$ with two points $p_1$ and $p_2$ on it and am looking for an explicit degree seven cover $X\to E$ with ramification precisely over $p_i$, with a single preimage ...
- 5,186
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
1
vote
0
answers
36
views
Does Hoffman constant keep the same after a very tiny perturbation on the polyhedron such that the bases are even unchanegd?
Suppose that $P$ is a polyhedron represented by
$$P:=\{x \in \mathbb{R}^n: A x \le b \} \text{ for }A \in \mathbb{R}^{m\times n},\ b \in \mathbb{R}^m,$$
and $P$ contains interior points. Moreover, the ...
- 33
3
votes
2
answers
232
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.
...
- 5,979
3
votes
0
answers
141
views
Optimal intersections between planar convex regions
Here is an earlier discussion that could be related:
On comparing planar convex regions of equal perimeter and area
We are broadly interested in placing two given planar convex regions so that the ...
- 5,979
1
vote
0
answers
47
views
Nash Equilibria change linearly in (some) game parameters. Already known / follows from a more general result?
EDIT: The key thing that I am wondering about is the linearity of the P2 strategy, not the constancy of P1. (The latter is straightforward.)
Question: Is the following result already known? Or is it a ...
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
1
vote
0
answers
46
views
Computational hardness of a discrete generalized rectangle packing problem
I have a decision problem that is clearly in NP, but I cannot seem to prove that it is in P, nor can I prove its NP-hardness. I attribute this more to my inexperience than to the problem's difficulty (...
1
vote
0
answers
258
views
How to do an elevated 2D Delaunay triangulation?
This is what I call an elevated Delaunay triangulation:
This is also called a 2.5D Delaunay triangulation.
To do it, I simply perform an ordinary 2D Delaunay triangulation with the (x,y)-coordinates, ...
- 2,560
2
votes
1
answer
644
views
How to maximise infinity norm of $x$ with constraint $Ax \le b$ using linear program? [closed]
I want to maximise the infinity norm of $x$, subject to constraint: $Ax \le b$. I think you can use a linear program to solve this, but how do you go about formulating it?
3
votes
1
answer
143
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 ...
- 5,979
2
votes
0
answers
154
views
Reduced Voronoi diagram
I am currently reading Differentiable Surface Triangulation presented at Siggraph Asia 2021.
I think most of the paper is clear to me, though I keep re-reading through to see if I miss details.
The ...
- 115
2
votes
0
answers
78
views
The fastest way to sample points on an implicit manifold, or projecting points on a manifold
Given a compact manifold $M$ in $R^n$, $M = f(x)$, f(x) is infinitely differentiable. $x$ $\in$ $R^n$, I want to find a bunch of samples on the manifold.
Currently, I'm setting up an SQP optimization ...
- 21
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
0
votes
1
answer
143
views
$\mathrm{ILP}$-formulation for Minimum Maximal Matching (MMM) Problem
Despite some online searching I couldn't find examples of dedicated Integer Linear Programs ($\mathrm{ILP}$s) for determining smallest matchings, that are not contained in a larger one.
It seems that ...
- 13.2k
3
votes
0
answers
260
views
What is the VC-dimension of regular convex k-gons in the plane?
Recall the relevant definitions:
Let $H$ be a family of sets in $\mathbb{R}^d$. The intersection of $H$ with a point set $C$ is defined as $H\cap C = \{h\cap C\mid h\in H\}$. The VC-dimension of $H$ (...
- 131
2
votes
1
answer
66
views
Optimal unions of planar convex regions
This post continues Optimal intersections between planar convex regions.
Question: Given two planar convex polygonal regions $C_1$ and $C_2$, how does one algorithmically find how to place and orient ...
- 5,979
5
votes
1
answer
491
views
Check if a polygon has an axis of symmetry in $O(n)$ time
Question: Is it possible to check if an $n$-gon has an axis of symmetry in $O(n)$ time?
Note: An $O(n^2)$ algorithm is easy to see: it is easy to check if any given line is an axis of symmetry of the $...
- 5,979
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
8
votes
1
answer
935
views
Final project ideas - computational geometry
Next semester I am teaching (the programming part) of a course in Computational Geometry. There are 14 weeks of class, two "pure theory/blackboard" hours per week, one "theory/...
- 553
6
votes
1
answer
631
views
On covering convex 2D regions with rectangles
Given a convex 2D region $C$ and a positive integer $N$. We need to cover $C$ with $N$ rectangles such that the sum of the areas of the $N$ rectangles is the least – no further constraints on the ...
- 5,979
1
vote
0
answers
54
views
Dissection of polygons that preserve boundaries
Ref:
Inside-out polygonal dissections
Further queries on inside-out polygonal dissections
Question: Consider any two polygons P1 and P2 with equal area and equal perimeter. Is it always possible to ...
- 5,979
2
votes
1
answer
113
views
Existence of fine approximate of a convex body in $\mathbb R^d$ with convex hull of $\mathcal O(d)$ points
Let $K$ be a convex body in $\mathbb R^d$ which contains the origin and let $\theta \in (0,1)$.
Question. Is it always possible to find $n$ points $x_1,\dotsc,x_n \in \mathbb R^d$ such that
$$
\theta ...
- 6,853
0
votes
0
answers
115
views
Explicit equation for border of the Minkowski sum of sets
Assume we have sets of the form
$$
M_j = \{x\in\mathbb{R}^d : f_j(x) \le 0,x \ge 0\}
$$
where $x\ge 0$ means $x_i \ge 0 \quad \forall i=1,\dots, d$.
Goal
I am looking for an (explicit) representation ...
- 385
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
0
votes
1
answer
64
views
Round Robin volleyball Tournament [closed]
Consider a set of N teams (N even number) that must make a
Round Robin Tournament. To each pair i; j, i ≠ j, of teams there is associated level
of interest si,j ∈ {1;2;3} of the match between them (1 =...
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
0
votes
1
answer
82
views
Combining Dantzig-Wolfe and Benders decomposition
I'm now solving an LP that has a few coupling rows (as in Dantzig-Wolfe decomposition) and a few coupling columns (as in Benders decomposition) simultaneously; other rows and columns are block-angular....
- 3
1
vote
0
answers
38
views
Efficient solution to linear matrix equations
A general form for a linear matrix equation can be written as
$$AX + XB + \sum C_iXD_i$$
If $C_i$ and $D_i$ are all 0, then this simplifies into a well known and studied matrix equation that has an ...
- 11
3
votes
1
answer
402
views
Computing intersections of unit disks
Given $n \geq 2$ points in the plane, how can one efficiently (or even inefficiently!) compute the number of corner-points belonging to the boundary of the intersection of the unit disks centered on ...
- 19.7k
1
vote
0
answers
30
views
Partitioning convex n-gons into least number of equal area convex quadrilaterals
This post adds a bit to Partitioning convex polygons into quadrilaterals of equal area and perimeter
Question: How does one achieve the partition of any given convex n-gon into the least number of ...
- 5,979
5
votes
2
answers
371
views
Is there an upper bound on the number of points in point cloud for which we compute the persistent homology?
I am interested in the topic of persistent homology (topological data analysis). According to what I read, there is some roadblock in the analysis of "big data" using persistent homology as it is ...
- 1,229
1
vote
1
answer
208
views
On a possible variant of Monsky's theorem
See Wikipedia for Monsky's theorem which states: it is not possible to dissect a square into an odd number of triangles all of equal area.
Questions: Are there quadrilaterals that allow partition into ...
- 5,979
1
vote
0
answers
59
views
How do I incorporate Ito's lemma into the solution for a finite-horizon stochastic cake-eating problem?
I'm interested in finite-horizon, continuous-time cake-eating problems in which the agent has a time-horizon $W$ over which to eat the cake, and then chooses an optimal consumption path $\{h_t\}_0^W$, ...
- 11
2
votes
1
answer
272
views
Triangulations of point sets — obtuse and acute triangles
Given a planar configuration of points in general position. It is known that the Delaunay triangulation is the 'fattest' triangulation possible. It is also easily seen that given 7 points with 6 of ...
- 5,979