Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [convex-hull]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
87 views

Non-convex optimization with correlated minima

I am thinking of non-convex optimization problems where the minima are somehow correlated. Maybe there are symmetry relationships among minima or maybe there is regularity in spacing among minima in ...
Omar Shehab's user avatar
1 vote
0 answers
42 views

Detailed exposition for proof of Localization Lemma in paper "Random Walks in a Convex Body and an Improved Volume Algorithm"

I've begun reading the paper "Random Walks in a Convex Body and an Improved Volume Algorithm" by Lovász-Simonovits ('93). Although the paper for the most part is pretty self-contained and ...
total dependent random choice's user avatar
3 votes
1 answer
112 views

Strongly polynomial time algorithm for shortest convex combination

Problem: Let $S$ be a finite set of vectors. Let $C$ be their convex hull. Compute $\operatorname{argmin}_{x \in C} \|x\|$. Reference 1 gives an algorithm for this problem that is finite-time (Section ...
user76284's user avatar
  • 662
1 vote
0 answers
73 views

How to enforce convexity?

I have a problem for which the solution is known to be a convex $f:[a,b]\times[c,d] \rightarrow \mathbb{R}$ over some rectangular domain ($a<b$ and $c<d$). There are many situations (e.g. ...
Yly's user avatar
  • 111
4 votes
1 answer
195 views

Restriction of a convex function to {0, 1}^n

Suppose I have a real-valued convex function $f$ on the unit hypercube $[0,1]^n$, and let $\bar{f}$ be its restriction to the integer points $\{0,1\}^n$. Does $\bar{f}$ satisfy any properties, or can ...
Sean L.'s user avatar
  • 43
3 votes
1 answer
228 views

Convex polygons inclusion relation

I have the following problem which came as a subproblem in some work I was doing and I am completely stuck. Note that I am interested in it only in terms of worst case time complexity (not heuristics ...
ioannis's user avatar
  • 41
1 vote
0 answers
17 views

Size of solutions in integer programming

Given a linear integer program $Ax\leq b$ with $A\in\mathbb Z^{m\times n}$ and $b\in\mathbb Z^m$ known is there a polynomial time algorithm to give tight upper bounds for $\log_2\|x\|_\infty$ and $\...
Turbo's user avatar
  • 12.9k
5 votes
0 answers
310 views

Total time complexity of convex hull problem

The convex hull problem is to compute the facets of the convex hull of finitely many given points in $\mathbb{R}^d.$ By cone polarity it is equivalent to computing the vertices and rays of a ...
user avatar
2 votes
1 answer
557 views

maximizing inner product

Given two lists $L,L'\subseteq\mathbb{R}^d$ of $n$ vectors each, how fast can we compute for all $p\in L$ the vector of $L'$ that maximizes the inner product with $p$, i.e., $\arg\max_{p'\in L'} \...
Joseph Stack's user avatar
  • 1,095
1 vote
0 answers
88 views

Convex hull of codebook (LP-decoding)

So the well-cited article by Feldman et al from 2005 has a method of constructing the convex hull of the feasible set for ML-decoding. Basically, he considers the parity check matrix $H$ as a Tanner ...
luegofuego's user avatar
2 votes
1 answer
267 views

When can a convex function induce submodularity?

Say I have a real valued convex function $f$ on the hypercube $[-1,1]^n$. Let $f'$ be the induced function on the discrete hypercube $\{-1,1\}^n$. Now I want to find a vertex on $\{-1,1\}^n$ on which ...
Student's user avatar
  • 654
1 vote
0 answers
29 views

Extending Delaunay graphs in d-space

I am new to computational geometry so pardon me for the lack of formalism. I am currently experimenting with an algorithm of mine in which I need to extend recursively a Delaunay graph in $d$-space. ...
Jonathan H's user avatar
3 votes
1 answer
1k views

Time complexity of d-dimensional convex hull

Consider the convex hull problem in $\Re^d$: Input: a list of $n$ points $S$ in $\Re^d$, Output: the vertices of the convex hull of $S$. What is the best lower bound on the time complexity of ...
user avatar