All Questions
985 questions
0
votes
1
answer
103
views
Constrained linear optimization problem on $C^1$
I am dealing with a problem of the form ($a<b$)
$$
\displaystyle \max_{v \in C^1([a, b])} \int_a^b v(x)~\mathrm{d}x, \quad \mathrm{s.t.} \int^b_a \big(-o'(x)v(x)-v'(x)o(x)\big)f(x)~\mathrm{d}x \...
1
vote
1
answer
127
views
Smallest trapeziums containing a given convex n-gon
Question: Given a planar convex $n$-gon $C$, to find the smallest area / smallest perimeter trapezium (trapezoid) - a convex quadrilateral with at least one pair of mutually parallel edges - that ...
- 5,979
3
votes
0
answers
65
views
Cutting triangles into triangles with equal longest side
This post elaborates on a specific instance of Cutting convex polygons into triangles of same diameter .
Question: For any integer n, can any triangle be cut into n non-degenerate triangles all of ...
- 5,979
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
0
votes
0
answers
145
views
Bound on solutions of $Ax \ge b$
Let $A \in \mathbb{Z}^{m \times n}, b \in \mathbb{Z}^{m \times 1}$.
One can show that if there is a solution of $Ax \ge b, x \in \mathbb{R}^n$ then there is one such that $\|x\|_{\infty} \le c (\|A\|_{...
- 439
0
votes
0
answers
84
views
1-degree SOS proof refutes Linear Programming
I am trying to understand Sums-of-Squares proof systems.
A degree $d$ Sums-of-Squares refutation for a set of polynomial equations $P = \{p_1(x) = 0, ..., p_m(x) = 0\}$ is defined as
$\sum_{i=1}^m g_i(...
1
vote
1
answer
119
views
Adding linear constraint to the domain
I don't know if it is a well-known problem, but I have been struggling to come up with an algorithm.
I have a set of linear constraints $Ax\le b$, $b\ge 0$ ($b$ and $A$ are given, $x$ is a variable). ...
2
votes
1
answer
154
views
Do there exist smaller simplicial models of barycentric subdivisions?
Let $S$ be a simplicial complex and let $Bary(S)$ denote its barycentric subdivision.
Of course, the geometric realizations of $S$ and $Bary(S)$ are homeomorphic.
However, one issue that arises in ...
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
0
votes
1
answer
51
views
What is the most dense sample for which the Crust algorithm returns an incorrect polygonal reconstruction?
The Crust algorithm by Amenta, Bern, and Eppstein computes a polygonal reconstruction of a smooth curve $C$ without boundary from a discrete set of sample points $S$. It is known that if $S$ is an a $\...
- 413
-2
votes
1
answer
248
views
Are there any non-elementary functions that are computable?
Does a function $\mathit{f}:\mathbb{R}→\mathbb{R}$ being non-elementary (not expressible as a combination of finitely many elementary operations), imply that it is not computable?
The particular case ...
- 11
1
vote
0
answers
335
views
Closed-form solution of a particular linear program
(Note: I asked a similar question at math.stackexchange but the present one is more precise.)
I have a linear program of the form:
$$\text{minimize} \space\space x_1 \space\space \text{subject to:}$$
$...
- 990
5
votes
1
answer
255
views
Counting points above lines
Consider a set $P$ of $N$ points in the unit square and a set $L$ of $N$ non-vertical lines. Can we count the number of pairs $$\{(p,\ell)\in P\times L: p\; \text{lies above}\; \ell\}$$ in time $\...
- 20.2k
5
votes
0
answers
167
views
Computing sums with linear conditions quickly
Let $f:\{1,\dotsc,N\}\to \mathbb{C}$, $\beta:\{1,\dotsc,N\}\to [0,1]$ be given by tables (or, what is basically the same, assume their values can be computed in constant time). For $0\leq \gamma_0\leq ...
- 20.2k
1
vote
0
answers
86
views
Explicit form of boundary operators of topological cones
Let $\Omega$ be a regular, finite, $n$-dimensional CW complex with chain modules $\mathscr{C}_k$ and boundary operators $\partial_k$.
For many problems in computational geometry, a key operation is to ...
- 840
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
3
votes
1
answer
111
views
Constrained morphing of polygons
This post continues 'Constrained morphing' of planar convex regions
If an $m$-gon $P_m$ is to be morphed (altered continuously) into an $n$-gon $P_n$ with same area and perimeter, can one ...
- 5,979
2
votes
1
answer
84
views
'Constrained morphing' of planar convex regions
Morphing may be defined as a continuous transition of one shape to another. This post is about modifying planar regions continuously from one form to another under some constraints.
Qn: If $C_1$ and $...
- 5,979
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 (...
2
votes
1
answer
61
views
Counting the number of pair of d-uplets with upper bounded distance
Consider two d-uplets $u = (u_1,...,u_d)$ and $v = (v_1, ..., v_d)$ both living in $\mathbb{N}^d$ with $d$ a positive integer. They both verify $$(*) \sum_{i=1}^d u_i = \sum_{i=1}^d v_i = k$$ with $k$ ...
- 55
0
votes
1
answer
147
views
Is there a redundant constraint in linear programming? [closed]
From wikipedia:
But... Why do we need the $x\ge 0$ part? We can instead do $-x\le 0$, and thus saving a line in the definition (which is not a big deal but nevertheless nice).
(In order to do that, ...
- 3
0
votes
0
answers
272
views
Finding the eigenvectors of a submatrix
Let $A=(a_{kl})$ be a matrix in $M_n(\mathbb{R})$ when $n$ is even. Let $B=(b_{kl})$ be the symmetric $2n$ by $2n$ matrix whose entries are given by,
$b_{k,l}=a_{kl}$ if $1\leq k,l\leq n$.
$b_{n+k,l}=...
- 4,058
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 ...
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
0
votes
1
answer
83
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
3
votes
0
answers
144
views
Hemisphere containing the maximum number of points scattered on a sphere
Consider a set of points $x_1, \ldots,x_n$ on $\mathbb{S}^{k-1}$ (the unit sphere in $\mathbb{R}^k$). The goal is finding the hemisphere which contains the maximum number of $x_i$'s. Basically, we ...
- 127
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
3
votes
1
answer
107
views
Results in computational geometry utilizing doubling dimension of a metric space
According to Wikipedia,
However, many results from classical harmonic analysis and computational geometry extend to the setting of metric spaces with doubling measures.
My question is: what are some ...
1
vote
0
answers
110
views
Upper bound on the diameter of a convex lattice n-gon with a given area
Given the area $A$ of a strictly convex polygon with $n$ vertices with integer Cartesian coordinates, there are usually several non-equivalent polygons. The relationship between the area, the number ...
- 206
1
vote
0
answers
78
views
Triangulation of polygons with all triangles having a common angle
Following Partition of polygons into 'strongly acute' and 'strongly obtuse' triangles, we record another triangulation question.
Question: Given an n-vertex polygonal region ("n-...
- 5,979
6
votes
2
answers
215
views
Partition of polygons into 'strongly acute' and 'strongly obtuse' triangles
Definition: Let us refer to obtuse triangles with the largest angle strictly above a given cutoff value as 'strongly obtuse' - the definition is parametrized by the cutoff value. Likewise, strongly ...
- 5,979
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
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
0
votes
1
answer
93
views
How quickly can this IQP or its MILP relaxation be solved
Let $A\in\{0,1\}^{(n,n)}$ be a $n$ by $n$ boolean matrix (in particular think of an adjacency matrix of a graph), and consider the following optimization problem:
$$\begin{align*}&&\max_{P\in\{...
- 71
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
0
votes
1
answer
539
views
Method for (binary) optimization under constraints
I would like to know if there is a method to solve the Problem.
Problem:
Maximize the following function: $$f(p_{1,i},p_{2,i},\dotsc,p_{m,i})=\sum_{i=1}^{n}\begin{bmatrix}p_{1,i} & p_{2,i} & \...
- 3
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
0
answers
197
views
Is orthogonal polygon with crossings count NP-complete?
The are several NP-complete problems related to the construction of orthogonal simple polygons. Rapport showed that it is NP-complete to decide the existence of orthogonal simple polygon that passes ...
- 2,993
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
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
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
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
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
1
vote
1
answer
181
views
Linear programming with "nice" matrices
Consider the following linear programming problem
\begin{array}{ll}
\text{minimize} & \mathrm 1^{\top} \mathrm x\\
\text{subject to} & v\le \mathrm A \mathrm x \le u\\
& \mathrm x \geq ...
- 650
11
votes
1
answer
410
views
Complexity of counting regions in hyperplane arrangements
Let $H_1,\ldots,H_n$ be hyperplanes in $\Bbb R^d$. Denote $\mathcal{H} :=\{H_1,\ldots,H_n\}$ and let $c(\mathcal{H})$ be the number of regions in the complement: $\Bbb R^d\setminus \bigcup H_i$.
...
- 17k
1
vote
0
answers
62
views
What are some other methods for partitioning an n-dimensional space based on a set of points in that space?
So this is a very general question, but I'm curious if there are any other methods for partitioning an n-dimensional space based on the location of a set of points, either randomly chosen or specified,...
- 11
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
9
votes
0
answers
289
views
Computer algebra tools for finding real dimension of an algebraic variety
I have a system of polynomial equations with the unknowns being real numbers. The set of solutions is infinite. What software can I use to compute the real dimension of the solution set?
The CAD-based ...
- 175
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
2
votes
1
answer
876
views
Interpreting mincost flow dual variables
Consider the task of finding flow of size $b$ with minimum possible cost.
It may be formulated as linear programming in a following way:
$$\boxed{\begin{gather}
\min\limits_{f_{ij} \in \mathbb R} &...
- 1,171