All Questions
985 questions
4
votes
2
answers
440
views
largest diameter of intersection of two balls
Two closed balls with a common radius are positioned so that the centre of either ball is on the boundary of the other.
I am interested in the extremal diameter of their intersection, in an arbitrary ...
- 6,001
7
votes
1
answer
386
views
Which zero-diagonal matrices contain the all-one vector in their columns' conic hull?
Let $A$ be a non-negative zero-diagonal invertible matrix. Which $A$ make the following assertions true, which are all equivalent:
The all-one vector $j$ is contained in the conic hull of $col(A)$.
...
CommunityBot
- 1
0
votes
1
answer
145
views
How to solve this optimization problem efficiently? [closed]
Let, $D\in\mathbb{C}^{1\times M}$ is a row vector with $M$ elements
$V\in\mathbb{C}^{3^M\times M}$ is a given matrix
$T$ is a scalar (real and $>1$)
$\textbf{The problem at hand is as follows:}$
...
- 111
1
vote
1
answer
123
views
LASSO problem but with a maximization instead of minimization
I have the following optimization problem (like the LASSO problem but with maximization instead of minimization):
$\mathbf{maximize}_{\boldsymbol{\alpha}} \|\mathbf{x} -\mathbf{A}\boldsymbol{\alpha}\|...
- 20.2k
3
votes
1
answer
516
views
On using a 3D convex hull to compute a 2D Voronoi diagram
I am working in a computing environment that has the facility to compute general nD convex hulls and not much else in the way of computational geometry. The routine, given a set of points, gives the ...
- 151k
2
votes
1
answer
69
views
Compute the hull of nonnegative linear combinations of a finite set, and the extreme points of the intersection of two polyhedra
Let $\mathbb{R}^d$ be $d$-dimensional Euclidean space
Let $\Delta=\{x\in\mathbb{R}^d_+:\sum_{i=1}^dx^i\leq1\}$ ($x^i$ is the i-th coordinate of $x$)
(Equivalently, $\Delta$ is the convex hull of $\{(0,...
- 151k
-1
votes
1
answer
88
views
sparse data fitting problem [closed]
I am a new learner of optimization, and I am confused by the question below, (how to change a 0-norm constrain into binary and linear constrain ?)
Given a sparse data fitting problem:
$ minimize \...
- 1,517
4
votes
2
answers
734
views
Fast projection onto a subspace
Given an $n$-dimensional vector $\mathbf{c}\in [0,1]^n$, let $\Delta_{\mathbf{c}}$ be the set of points $\{\mathbf{x}\in [0,1]^n: \langle \mathbf{c},\mathbf{x} \rangle \le 1\}$, where $\langle \mathbf{...
- 12.7k
5
votes
2
answers
433
views
Checking a Guarding for the Art Gallery Problem
In the Art Gallery Problem, we have given
a polygon $P$ on $n$ vertices and a number $k$ and we
want to know if there exists $k$ guards
such that every point inside the polygon
is seen by at least ...
- 479
4
votes
2
answers
424
views
Algorithm for Reconstructing Point Sites from a Voronoi Diagram
how can one construct a finite set of points in the euclidean plane from its Voronoi Diagram and, what is the complexity of the problem?
- 151k
2
votes
2
answers
124
views
Monotonicity for the side lengths of stars inscribed in regular polygons
Fix integers $l\ge 1$ and $n \ge 3$, and let $P_n$ denote the boundary of the regular $n$-sided polygon in the plane. We define a $(2l+1)$-pointed equilateral star to be a cyclically ordered list of ...
- 23.7k
3
votes
2
answers
381
views
Cone-Torus intersection in 3D
Problem. I have a solid torus and a solid cone in $\mathbb R^3$ and need an efficient algorithm that determines if they intersect or not.
The center of the torus is at a given position $\mathbf p \in ...
- 6,891
4
votes
2
answers
805
views
Fitting one Polygon in another
I have two Polygons A and B and I want to find the position, rotation and scale of B, so it fits into A and has the maximum Area possible. Also both can be concave.
I did some research but couldn't ...
- 4,713
1
vote
0
answers
74
views
How to minimize n-polytope's bounding box with linear transformation?
I am working on an exact algorithm for integer linear programming for my master's thesis:
$Ax\leq b, x \in \mathbb{Z}^n$
$cx\rightarrow min$
For my idea to work out, I need a guarantee that n-...
- 11
3
votes
1
answer
99
views
How to value the extent of separation or mixing of point sets in plane?
As the image presented below, the reddish point set is totally separated from the blueish one and the greenish one, while the blueish point set is quite mixed with the greenish one.
A number of ...
- 128k
2
votes
2
answers
171
views
Discrete approximation of Minkshisundaram-Pleijel zeta function?
I'm looking for some references on the following situation:
$S$ is a Riemannian surface, and $G_n$ is a sequence of metric subgraphs embedded on $S$. Let $\zeta_n$ be the zeta function of the ...
- 1,462
5
votes
2
answers
440
views
Ascertain properties of a new kind of rectilinear-convex set
PREABMLE TO MY QUESTION
I am reading about convex sets and hulls in orthogonal/rectilinear spaces. As can be seen in this publication, for a given set of points in $\mathbb{R}^{2}$, there are many ...
CommunityBot
- 1
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,...
- 13.6k
1
vote
0
answers
85
views
"Barrier functions" in function spaces [closed]
In general the idea of a "barrier function" (as in the context of "interior point methods") can possibly be thought of as defining a function corresponding to an open subset of $\mathbb{R}^n$ such ...
- 2,246
0
votes
1
answer
490
views
Relax a rectangular linear assignment problem
I wonder if there is any literature on the following problem
$$\begin{array}{ll} \underset{X \in \mathbb R^{m\times n}}{\text{minimize}} & \displaystyle\sum_{i,j} C_{i,j} X_{i,j}\\ \text{subject ...
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 $\...
- 101
3
votes
1
answer
119
views
Shortest Manhattan-norm paths among disjoint rectangles
I am looking for the fastest possible algorithm for solving the following problem: I am given a collection of disjoint axis-aligned rectangles in the plane, and I need to pre-process these rectangles ...
- 151k
4
votes
3
answers
957
views
Questions on Discrete Exterior Calculus in numerical computing
I have several questions about Discrete Exterior Calculus (DEC) in numerical methods for solving partial differential equations in physics:
(Discrete Exterious Calculus is a newly developed subject ...
- 201
2
votes
1
answer
502
views
Feasibility Mixed integer Linear programming with quadratic constraints?
Consider the mixed integer program
$$Ax\leq b$$
$$By\leq c$$
$$\begin{bmatrix}x&y\end{bmatrix}C\begin{bmatrix}x\\y\end{bmatrix}+D\begin{bmatrix}x\\y\end{bmatrix}\leq d$$ where $x$ are integer ...
- 1,517
3
votes
1
answer
266
views
Strong polynomial algorithm for linear programming
What is the current state of finding a strong polynomial algorithm for linear programming? Is there any reference?
-1
votes
2
answers
114
views
On OR condition in Linear Programming with exponentially many constraints [closed]
Suppose we have two linear programs $Ax\leq b$ and $Bx\leq c$ is there a way to combine them into one program of possibly a larger dimension $Cy\leq d$ such that projection of vectors $y$ into a ...
- 128k
0
votes
0
answers
99
views
Is this Graph Iteration Already Known?
When attempting to set up an ILP formulation for a weight-minimal cubic spanning tree (i.e. one with vertex degrees either 1 or 3) I needed connectivity constraint, but misremembered the contents of ...
CommunityBot
- 1
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 ...
- 761
0
votes
0
answers
46
views
linear inequalities and reference request
I have proved and am using the following simple lemma in my current research problem:
Let $\{a_1,...,a_m\}$ and $\{b_1,b_2,...,b_n\}$ be set of positive numbers such that $\sum_{i=1}^m a_i < \sum_{...
- 1,269
4
votes
2
answers
349
views
How many dihedral angles need to be specified to uniquely specify a triangulated polyhedron?
Suppose you are given a simplicial complex $K$ homeomorphic to the sphere and for each each edge of the complex a label specifying a length of that edge (this gives us a polyhedral metric on $K$). In ...
- 151k
1
vote
1
answer
169
views
Optimization of a continuous function
This is more like an optimization problem but any solution is appreciated.
I have a data set with input specifying power(demand) to be generated for a particular time period(TP).
Input:
Time --- ...
- 61.9k
3
votes
2
answers
437
views
convex polytope integer points
is there a simple proof for the following lemma:
An unbounded convex polytope (defined by linear constraints) has either zero integer points or infinite many integer points.
- 1,991
1
vote
0
answers
66
views
On number of solutions by simplex and number of solutions in total in a linear optimization problem?
This is more of a clarification query.
Mizuno http://www2.ims.nus.edu.sg/Programs/012opti/files/talk_mizuno1.pdf says if we give a linear optimization problem
$$\max c'x$$
$$Ax\leq b$$
where $A\in\...
CommunityBot
- 1
2
votes
0
answers
74
views
Possible ordering of coordinates in a linear subspace [closed]
This question was asked on Mathematics Stack Exchange with no answers.
Let $X$ be a linear subspace of $\mathbb{R}^n$. For how many permutations $p$ on $1,...,n$ does there exists $x$ in $X$ with $...
- 2,821
2
votes
1
answer
91
views
Linear program with one quadratic condition convex in domain of interest polynomial time solvable?
$c\leq xy$ is not a convex condition.
However we know $c\leq xy$ is convex in domain $x,y>0$ in $\mathbb R^2$ for any fixed $c\in\mathbb R$.
Is $c\leq x_1y_1+\dots+x_ny_n$ with $0\leq x_1,\dots,...
- 54.2k
1
vote
0
answers
62
views
LP Constraints for Bridgeless Cactus Graphs
When trying to determine the optimal bridgeless spanning cactus graph of a weighted, symmetric graph, I got stuck.
What I do not know how to capture, is
the variable number and sizes of the cycles
...
CommunityBot
- 1
5
votes
1
answer
445
views
Minimum euclidean spanning tree in n dimensional space
I need to compute the minimum euclidean spanning tree in $R^d$ and do it with some algorithm that can do it with complexity near to $\Omega(nlogn)$ where $n$ is the size of the point set.
Right now I'...
- 151k
0
votes
0
answers
368
views
Finding a point in the relative interior of the convex hull of a set of integer-valued vectors
Let $X \subset \mathbb{Z}^n$ be the set of integer-valued vectors satisfying a system of linear constraints. We can suppose that $X$ is the set of integral points in a given polyhydral set $Y \subset \...
- 136
1
vote
0
answers
60
views
On the defect of a flow network
This problem in graph theory was actually motivated by some problems in Theory of Fractals.
To formulate the problem I need to recall some definitions related to flow network.
A flow network is a ...
CommunityBot
- 1
1
vote
0
answers
86
views
Infinite system of equations with finitely many constraints
During my research I have stumbled upon the following issue concerning infinite systems of linear equations. I do not have much practice in such settings, so I am asking you whether the following ...
2
votes
0
answers
111
views
How to compute explicit equations for the Jacobian of a variety over a field [duplicate]
Suppose we start with a projective curve $X$ over a field $K$, given as a closed subvariety of $\mathbb P^n_K$ by some explicit list of equations. I would like to find an explicit representation of ...
- 374
2
votes
2
answers
687
views
Where to submit a new convex hull algorithm?
Recently, I devised a new convex hull algorithm. Is there any forum where I can submit my work?
- 4,713
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 ...
6
votes
1
answer
2k
views
Approximation of convex hull in high dimension
What are efficient methods (polytime) to compute an approximation of the convex hull in high dimension (say, $30000$) for a given set of points?
Edit:
I am looking for an algorithm for getting the ...
5
votes
0
answers
162
views
Homogeneous linear and quadratic inequalities
I have a bunch of vectors $b_i \in R^n$ for $i = 1,\ldots,N$ and a bunch of (indefinite) matrices $A_j$ for $j = 1,\ldots,M$. Let's consider the set $S \subset R^n$ of $x \in R^n$ vectors such that
$$...
4
votes
0
answers
123
views
Cylindrical Decomposition vs Morse decomposition
Suppose I have a polynomial Morse function $f: \mathbb{R}^n \to \mathbb{R}$. Consider the ideal $I(\nabla f)$ generated by the partial derivatives $\partial_i f$, and assume that the real zero-set of ...
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|.$$
...
1
vote
0
answers
117
views
The upper bound of the number of points of a convex hull formed by external co-tangents of circles
Consider the following problem: Given a rope to surround some circles, and minimize the length of the rope.
In order to solve the problem, we shall calculate all external co-tangents of these circles, ...
- 601
1
vote
0
answers
246
views
How to solve a large linear programming problem? [closed]
I have the linear programming problem in $\mathbf x \in\mathbb R^n$
$$\begin{array}{ll} \text{minimize} & \mathbf c^T\mathbf x\\ \text{subject to} & \mathbf A\mathbf x \leq \mathbf b\end{...
1
vote
2
answers
269
views
Convergence of an iterated sequence
Let $K=[0,1]^2$ be a square and $p\in (0,1)$ be a fixed number. We define a map $F: K^2\to K^2$ as follows.
For $(x_1,y_1), (x_2,y_2)\in K$, it follows by a straightforward computation that there ...
CommunityBot
- 1