All Questions
984 questions
3
votes
0
answers
51
views
testing whether a polyhedral complex is convex
Definitions
A (polyhedral) cone in $\Bbb R^n$ is the solution set of a finite number of inequalities of the form $a_1x_1+\cdots+a_nx_n\geq 0$. Note that I don't require strict convexity, i.e. a cone $...
- 3,079
2
votes
0
answers
362
views
Rational integer solutions of a linear Diophantine equation of cyclotomic integers
I am working with lattices in $\mathbb{C}$, and I want to know whether a certain vector is an element of the lattice.
In particular, suppose my lattice vectors are $a$ and $b$ and I want to know ...
- 63.9k
0
votes
1
answer
131
views
How hard is a linear programming with a bounded constraint?
Background: I am reading Greg Kuperberg's answer to the question Deciding membership in a convex hull. I am thinking about the complexity of ''Deciding membership in a convex hull''.
Restate the ...
- 63.9k
1
vote
0
answers
46
views
Multi-layered wrapping of polyhedra
This post continues from How big a box can you wrap with a given polygon? and Convex polyhedra that can be folded from convex polygons. One can also mention 'k-fold coverings of the plane' as examined ...
- 63.9k
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 ...
- 151k
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
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
0
votes
1
answer
214
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 ...
- 1,714
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,492
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 ...
- 63.9k
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 ...
- 7,226
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
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:...
- 169
8
votes
1
answer
316
views
What is the form of the $(v_0,v_1)$-pizza curve?
Assume that there are two (competing) pizza houses situated at the points $0$ and $1$ on the complex plane. These pizza houses can deliver pizza to points of the plane with the largest velocities $v_0$...
- 12.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 $\...
- 14k
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
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
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 ...
- 5,429
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
8
votes
2
answers
339
views
Angle subtended by the shortest segment that bisects the area of a convex polygon
Let $C$ be a convex polygon in the plane and let $s$ be the shortest line segment (I believe this is called a "chord") that divides the area of $C$ in half. What is the smallest angle that $s$ could ...
- 3,065
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 ...
2
votes
3
answers
752
views
Reference Request for Integer factorization with LP/ILP
Have there been attempts to factor integers with Linear Programming?
Searching the internet suggests that for Integer Factorization only Number Theoretic algorithms, like sieves, are taken into ...
- 13.2k
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 ...
- 3,772
2
votes
1
answer
591
views
Intersection of a vector subspace with a cone
Given a set of vectors $S=\{v_1, v_2,...,v_d\} \subset \mathbb{R}^{N}, \, N>d$, is there any algorithm to decide if there exist a vector with all coordinates strictly positive in the generating ...
- 6,962
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
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 ...
- 5,429
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 $...
- 151k
0
votes
1
answer
1k
views
Fast way to generate random points in 2D according to a density function
I'm looking for a fast way to generate random points in 2D according to a given 2D density function.
For instance something like this:
Right now I'm using a modified version of "Poisson disc&...
CommunityBot
- 1
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 ...
4
votes
1
answer
204
views
Reference: Packing under translation is in NP
I am looking for a reference for a result that I am aware of.
Let me describe the result.
Given a polygon $C$ and polygons $p_1,\ldots,p_n$, it can be decided in NP
time, if $p_1,\ldots,p_n$ can be ...
CommunityBot
- 1
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:
...
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 ...
- 28.2k
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 ...
- 151k
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 ...
- 151k
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 ...
- 3,065
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 ...
- 5,971
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
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
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
7
votes
3
answers
2k
views
Algorithm to compute the Voronoi diagram of points, line segments and triangles in $\mathbb{R}^3$
Is there a known algorithm to compute the (generalized) Voronoi diagram of a set of points, line segments and triangles in $\mathbb{R}^3$? If yes, are there any available implementations?
I know that ...
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 ...
- 34.3k
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/...
- 151k
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
5
votes
1
answer
388
views
Calculating $n$-dimensional hypervolumes ($n \sim 50$), for example
I have a question regarding efficient and possibly simple algorithms for computing volumes of $n$-dimensional polytopes.
The polytope of concern isn't arbitrary: it is obtained by applying a linear ...
- 141
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 ...
- 63.9k
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 ...
CommunityBot
- 1
6
votes
1
answer
424
views
Probability of intersecting a rectangle with random straight lines
We are given a rectangle $R$ with sides lengths $r_1$ and $r_2$, contained in a square $S$, with sides lengths $s_1=s_2\ge r_1$ and $s_2=s_1\ge r_2$. $R$ and $S$ are axis-aligned in a cartesian plane $...
- 1,677