All Questions
984 questions
2
votes
1
answer
116
views
Convex polyhedra that can be folded from convex polygons
This question is based on http://www.science.smith.edu/~jorourke/Papers/FoldingPP.pdf.
Therein is stated the theorem: Every convex polygon folds to an infinite number (a continuum) of noncongruent ...
- 5,979
6
votes
0
answers
219
views
How big a box can you wrap with a given polygon?
Question: Given a convex polygonal region, how does one find the box (rectangular parallelopiped) of maximum volume that can be wrapped with this region? While wrapping, if needed, some portions of ...
- 5,979
2
votes
0
answers
117
views
Folding polygons into 'vessels'
This question is based on http://www.science.smith.edu/~jorourke/Papers/FoldingPP.pdf
Define an vessel as a convex polyhedron with one face removed - in other words, a vessel can be converted into a ...
- 5,979
3
votes
0
answers
282
views
Continuum of Lagrange multipliers, duality gap, and minimax theorem
Suppose I have a linear optimization problem involving random variables on some (infinite) probability space $\Omega$. For example, need to maximize expectation $E[Q]$ of random variable $Q$ subject ...
- 781
0
votes
1
answer
213
views
How do you call a linear programming problem when the solution should be "constrained" to a norm?
(apologies for the n00b question)
Let's say we have a vector of length $n$, with to-be-determined values: $a_1, a_2, ...,a_n$.
And we have information that partial sums of these elements are equal to ...
- 143
1
vote
0
answers
67
views
Further queries on inside-out polygonal dissections
The following is based on Inside-out polygonal dissections
Definition: We say that a polygon P has an inside-out dissection into another polygon P' if P′ is congruent to P, and the perimeter of P ...
- 5,979
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
87
views
On vertices on convex smooth closed surfaces
Question: Given a smooth, convex, closed surface. How would one find points on it with the property: the average of the geodesic distances from that point to all other points on the surface (the ...
- 5,979
1
vote
1
answer
51
views
On triangulations and "coverage" of circumcircles
Let $P$ be a convex quadrilateral defined by four vertices $a$, $b$, $c$, and $d$. Suppose that the circumcircle of $\triangle abd$ contains $c$.* Let $D(\triangle abc)$ to denote the area enclosed by ...
- 173
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
1
vote
1
answer
589
views
Line segment-triangle intersection algorithm [closed]
currently in my project I'm using signed tetrahedron volume to check whether a line segment intersects a triangle. Initially I've found this approach in the great answer provided by professor O'Rourke:...
- 11
3
votes
0
answers
175
views
Cutting convex polygons into triangles of same diameter
This question continues from: Cutting convex regions into equal diameter and equal least width pieces
Definitions: The diameter of a convex region is the greatest distance between any pair of points ...
- 5,979
1
vote
0
answers
162
views
Optimization problem on trace of complex matrix product
Given a complex rectangular matrix $A$ $(k \times n)$, I am interested in solving the following optimization problem over $(k\times n)$ complex matrices $x$:
$$
\mathrm{arg}\max_X \,\mathrm{trace}(X^...
- 377
2
votes
0
answers
76
views
Polyhedron coordinate bound
Given a polyhedron
$$Ax\leq b$$
where we assume $A\in\mathbb Q^{m\times n}$ and $b\in\mathbb Q^{m}$ and it takes $L$ bits to represent the inequalities what is a good bound on the quantity $\|y\|_\...
- 13.9k
1
vote
0
answers
43
views
Detecting non-negativity of a single constraint by polyhedral constraints - $II$
Let $$\langle a,x\rangle=b$$ be a linear constraint where $x\in\mathbb R^n$ and every entry in $a=(a_1,\dots,a_n)$ is in $\mathbb Z_{\geq0}^{n}$ (non-negative) and the entry $b$ is in $\mathbb Z_{\...
- 13.9k
0
votes
1
answer
110
views
Detecting non-negativity of a single constraint by polyhedral constraints - $I$
We consider $$\langle a,x\rangle=b$$ (linear constraints) where $x\in\mathbb R_{\geq0}^n$ and every entry in $a=(a_1,\dots,a_n)$ is in $\mathbb Z_{\geq0}^{n}$ (non-negative) and the entry $b$ is in $\...
- 13.9k
0
votes
1
answer
116
views
Iterations of Dantzig-Wolfe Decomposition for a Simple Linear Programming problem
This arises from an engineering problem I am working on. Let $\mathbf{c}_i,\mathbf{a}_i,\mathbf{b}_i\in \mathbb{R}^{d}$ be a given set (collection) of vectors where $i\in\{1,\dots,n\}$. Define the ...
- 1,421
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
1
vote
1
answer
144
views
On convex polygons contained in convex polygons
In what follows '$n$-gon' stands for '$n$-vertex polygonal region'.
Question: Given a convex $n$-gon $C$, find the smallest convex region $R$ such that $C$ is the smallest $n$-gon that contains it.
...
- 5,979
0
votes
0
answers
93
views
Number of vertices in a polyhedron
Consider polytopes
$$A_1[x_{1,1},\dots,x_{1,m_1},z_{1}]'\leq b_1$$
$$A_2[x_{2,1},\dots,x_{2,m_2},z_{2}]'\leq b_2$$
$$B[z_{1},z_{2},z]'\leq c$$
having vertex count $v_1,v_2$ and $v$ respectively.
We ...
- 13.9k
1
vote
1
answer
115
views
$\mathrm{LP}$ formulation for $\mathrm{k}$-$\operatorname{opt}$ moves
$\mathrm{k}$-$\operatorname{opt}$ moves are an idea to improve non-optimal Hamilton cycles in weighted symmetric graphs by exchanging $\mathrm{k}$ tour-edges with $\mathrm{k}$ edges that do not belong ...
- 13.2k
1
vote
0
answers
172
views
continuity of linear programming
I have the following conjecture:
Given a closed convex set $S \subseteq \mathbb{R}^n$ and one of its exposed face $F=\{x \in S \mid \pi x = \pi_0\}$, where $\pi x =\pi_0$ is the supporting hyperplane ...
- 37
1
vote
0
answers
48
views
Deployment and dispersion in triangular regions
Definitions (from C. Stanley Ogilvy's 'Tomorrow's Math'):
Deployment: To place a specified number $n$ of points (stations) in a region such that the maximum distance of any point in the region from ...
- 5,979
1
vote
1
answer
98
views
Optimality gap between a joint linear program and decoupled sub programs
Let $\mathbf{c}_i,\mathbf{s}_i$ be given entry-wise positive $n\times 1$ vectors for $i\in[1,\dots,d]$. Let $\tau, \alpha_1,\dots, \alpha_d$ be given positive constants.
Consider the linear ...
- 1,421
1
vote
0
answers
81
views
Algorithm for deciding feasibility of linear programs [closed]
Suppose I have the simple linear program
$$Ax \geq 0, \quad x \geq 0$$
We know that this system has a solution (for example, $x=0$). But, what if we made this rule for this system?
$$Ax \geq 0, \quad ...
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
1
vote
0
answers
920
views
Maximizing a piecewise-linear convex function
Crossposted on Operations Research SE.
I am working on an optimization problem where some of the terms of the objective function to maximize are expressed as a piecewise linear function of variables:
...
- 111
1
vote
1
answer
160
views
Total area of cuboids projected on plane
Lets define n arbitrarily scaled, rotated, located cuboids, and plane by normalized direction vector.
Cuboids is supposed to be "flattened" by orthogonal projection on the plane, so we can ...
- 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
2
votes
0
answers
174
views
Random sets of points and hyperplanes in high dimensions
We are given a set $X$ of $n$ points $\mathbf{x}_1, \mathbf{x}_2, \ldots, \in\mathbb{R}^d$ selected uniformly at random from the unit origin-centered ball $\mathcal{B}^{d}$.
Consider the random ...
- 1,677
1
vote
0
answers
322
views
Decomposition of Polyhedral - An example
There is no doubt that clear examples consolidate the understanding of concepts being learnt. I am new to finding the structure and decomposition of a polyhedra. Suppose that we have the system
$$ \...
- 111
0
votes
1
answer
76
views
A question on graph partitioning
Given a connected un-directed simple graph $G=(V,E)$, is there a polynomial time algorithm to find the smallest subset $S$ of $V$ such that each node in $V \setminus S$ has at least 50% of its ...
- 1,216
1
vote
1
answer
1k
views
Check if a point is in the interior of the convex hull of some other points in high dimensions, and lower-bounding the largest enclosed ball [closed]
Given $m$ points $P=\{p_0, p_1, ..., p_m\}$ in high dimensions (e.g. 100), it is known that computing (or even representing) their convex hull $\text{conv}(P)$ is generally intractable due to the ...
- 11
3
votes
0
answers
87
views
Additional symmetries of the Traveling Salesman Polytope
Given the complete graph $K_n=(V,E)$, the Traveling Salesman Polytope is a convex polytope in $\Bbb R^E$ obtained as the convex hull of the indicator vectors of (edge-sets of) Hamiltonian cycles in $...
- 13.6k
1
vote
1
answer
157
views
Constructing representations of probability revision functions
Let $P$ be a probability distribution over a finite Boolean algebra $\mathfrak{B}$, and fix a parameter $t_{P} \in (\frac{2}{3}, 1)$. Define the `revision function of $P$', $R_{P}: \mathfrak{B}\...
- 631
1
vote
1
answer
628
views
Allowing an "OR" option between equations in a linear program
I am looking for a way to express an "or" option in a system of linear inequalities for a linear program I am working on.
I will explain what I mean precisely: Lets say I have a set of ...
- 141
6
votes
0
answers
157
views
On cutting disks from planar regions
Question: Given a planar region $R$ of unit area and an integer $n$, to cut $n$ circular disks (their sizes need not be equal) such that the highest fraction of $R$ is taken off.
A simple greedy ...
- 5,979
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
0
votes
0
answers
54
views
Attached convex "hulls"
Let $\mathcal{P}$ a finite set of points of a Euclidean $\mathbb{E}^n$ and take the union $\mathrm{U}(\mathcal{P})$ of all closed half-spaces defined by $n$ elements of $\mathcal{P}$ that contain only ...
- 13.2k
1
vote
0
answers
183
views
Using Bertini software to determine whether or not a variety is empty
I have a system of polynomials $f_1,\dots, f_n \in \mathbb{C}[x_1,\dots, x_m]$, and I would like to determine whether the set of solutions to the system $f_1(x)=\dots=f_n(x)=0$ is empty or not. Since ...
- 980
1
vote
0
answers
242
views
How to estimate the probability of an edge appearing in the minimum spanning tree of a graph?
I've been running into this problem recently and I've been stuck on it for a while.
I have a set of vertices $G$ that form a complete graph. From this I need to sample $k$ vertices (which would also ...
- 11
2
votes
0
answers
23
views
What is known about $\operatorname{card}_E(\mathrm{MST}\cap\mathrm{MWT})$?
It is a wellknown fact of computational geometry that the edges of Minimum-weight Spanning Tree are also found in the Delaunay Triangulation of a planar pointset $\mathcal{P}$, i.e. $\operatorname{...
- 13.2k
8
votes
2
answers
1k
views
Minesweeper as a linear algebra problem
I've written a computer program to generate and solve minesweeper games. Once I've eliminated the obvious mines and safe squares I look at each remaining connected setsin turn and formulate a linear ...
- 361
0
votes
0
answers
68
views
Convex optimization under asymmetric loss in infinite dimensional space
The following problem is common in financial economics
$$ \min_{m \in L^2} \mathbb{E}[ \phi(y(\theta)-m)] \quad \text{s.t. } \mathbb{E}[ mx ]= q $$
That is, given a random variable $y(\theta)$ ($\...
- 45
2
votes
1
answer
139
views
linear programming with $n$ choose $r$ variables
Given parameters $r < n$, define $m = {n \choose r}$ and let $A$ be the $n\times m$ matrix whose columns are all the vectors with $r$ $1$'s and $n-r$ $0$'s. Let $b$ be a positive $n$-vector. Is ...
- 51
2
votes
1
answer
763
views
Integer solution of optimal transport
Let us consider two vectors $\mathbf{a}=(a_1,...,a_n)$ and $\mathbf{b}=(b_1,...,b_m)$ so that each quantity is an integer $a_i,b_j \in \mathbb{N}$. It represents for example supply and demand. Let $\...
- 407
3
votes
1
answer
190
views
On some centers of convex regions based on partitions
These questions are inspired by Yaglom and Boltyanskii's 'Convex figures'.
Winternitz Theorem: If a 2D convex figure is divided into 2 parts by a line $l$ that passes through its center of gravity, ...
- 5,979
2
votes
0
answers
33
views
Algorithm for lightest unnested planar vertex-disjoint cycle-cover
Question:
given a finite set $\mathcal{P}$ of disjoint points in the Euclidean plane and the set $\mathcal{C}$ of all simple polygons whose corners are subsets of $\mathcal{P}$,
what is the ...
- 13.2k
1
vote
1
answer
3k
views
How to minimize l1-norm constrained by "infinity norm"
Let $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^m $. I have the following two problems:
P.1.
\begin{equation}
\underset{x\in\mathbb{R}^n}{\text{minimize}} \| Ax-b \|_1 \\
\text{s.t. } \| x \...
- 13
11
votes
0
answers
234
views
When is cohomology of a finitely presented dg-algebra computable?
Given a smooth affine variety $X$ defined over $\mathbb{Q}$, its singular cohomology is isomorphic to the algebraic de Rham cohomology, which is the cohomology of the complex $\Omega_X^0\to\Omega_X^1\...
- 3,772