4

Perhaps you want a hint first? Of course you start by considering all vectors $(a_i,b_i)$ first. The vector $(a_i,b_i)$ indicates the amounts you earn by working one hour on job $i$. What is the meaning of any point on the line segment between points $(a_i,b_i)$ and $(a_j,b_j)$? If any point $(a_k,b_k)$ is within the triangle $(0,0)$, $(a_i,b_i)$, $(a_j,...


4

A1) You're right, the algorithm description sounds kind of weird. A naive algorithm that takes exponential time would rather be something like foreach (R in S.subsets) if (R.isConvexHull(S)) return R However, the method for checking whether R is a convex hull needs $n$ time, so we obtain a runtime of $n2^n$. A2) Your premise is missing some ...


4

The simplest solution is to run two algorithms in parallel, one which runs in time $O(mn)$, and one which runs in time $O(n\log n)$. When one of the algorithms outputs a solution, you stop the other one. This runs in time $O(\min(mn,n\log n))$. In fact, you can do better – Wikipedia lists several $O(n\log m)$ algorithms, which is strictly better than the ...


4

So, the situation is that you have the vertices $\mathbf{v}_i$ of a polygon that defines a convex hull and a point $\mathbf{O}$ inside this polygon. Furthermore you have the vectors connecting $\mathbf{O}$ with each vertex of the polygon and the vertices are ordered. To construct a binary search algorithm that determines in which wedge the point $\mathbf{z}$ ...


3

It is not true. As you know, we can reduce sorting numbers to finding convex hull (see here). So, we know that size of the convex hull, in this case, is $N$. However, we can't compute convex hull in nearly linear time! as lower bound for sorting numbers in general case is $\Omega(n\log n)$. Anyhow, we have an algorithm to finding convex hull which is output-...


3

A pragmatic approach is just to use off-the-shelf black-box mathematical optimization algorithms. In particular, define parameters $\theta_1,\theta_2,\theta_3$, representing the angle from the horizontal of $D_1,D_2,D_3$, respectively. Here each $\theta_i$ is in the range $[0,2\pi)$. The locations of $D_1,D_2,D_3$ are completely determined by the value of ...


2

No, that's not a valid argument. You'd have to describe how to find which part of the triangulation is the convex hull, in $o(n \log n)$ time, to make that a valid argument.


2

I think this is correct... see 2. Chan’s Algorithm p4, Remark. Remark. Using a more clever search strategy instead of many binary searches one can handle the conquer phase in $O(n)$ time. However, this is irrelevant as far as the asymptotic runtime is concerned, given that already the divide step takes $O(n \log H)$ time. Anyway, the complexity is ...


1

A first order approximation is that convex programs are tractable, .i.e., most problems you can think of as a layman in the field that are convex, are (probably) tractable to solve. That's why you would be told that in an introductory course on convex optimization. It is not true though. Tractability of convex problems essentially boils down to being able ...


1

I eventually found an answer. The image of a hypercube in $\Bbb R^3$ under a linear map is called a zonohedron. They can be calculated efficiently, for example using the algorithm in An Efficient Algorithm for Generating Zonohedra (PostScript file) by Paul Heckbert.


1

Given a pair of points $A,B$, you can split the the data into the points that are to the left of the line $AB$ (or on the line) vs the points that are strictly to the right of $AB$. Then you can compute the convex hulls of these two sets and you can find the distance between the convex hulls in $O(n)$ time, for a particular split (use a Graham scan; pre-...


1

The edges examined never intersect because all points are first sorted in terms of angle from the starting point, and then traversed counterclockwise sequentially. By examining edges to each point sorted by their angle counterclockwise and never traversing clockwise (because you stop when you reach the starting node), you ensure that the edges won't interest....


1

I find it easier to prove the equivalent statement 'any pair $A,B$ such that the segment between them is a diameter of $P$ must be anti-podal': If the segment $s$ between $A,B$ is a diameter, construct the lines $k,l$ as follows: line $l$ is the unique line perpendicular to $s$ and through $A$. Line $k$ is the unique line perpendicular to $s$ and through $B$...


1

I'm assuming you asked about points on two-dimensional plane. Let $P_1$ and $P_2$ are these two points, such that the (Euclidean) distance $D$ between them is maximal over all the pairs of points in the given point set. All the other points must be inside an intersection of two disks with radius $D$ - one disk with center in the $P_1$ and another disk with ...


1

To turn a maximisation problem into a minimisation one (or vice versa), simply multiply the value by -1. Hence you want w1 * f1 - w2 * f2, for some appropriate choice of weights w1, w2 (which could indeed both be 1). Unless there's some other requirement you haven't mentioned, there's no specific need for w1 and w2 to add up to 1: it depends on the ...


1

I found a way to solve the problem in my case -- maybe that only applies to the special conditions found in the paper. There, the two point sets can be assumed to be non-collinear and always separable by a line parallel to one of the coordinate axes, and we always know that $A$ is "left of" (or "above") $B$. In this case, we can represent a line simply by $...


1

Graham scan for a convex hull works if you have an ordering of points $a_1,a_2,...a_N$ such that you have a sequence $p_1 < p_2 <...< p_k$ where your convex hull is $a_{p_1}, a_{p_2},...,a_{p_k}$ of which it is not possible to have a winding number greater than $1$. In general for any polygon $P$ this might not work, but for a star shaped polygon, ...


1

An SDP relaxation is not an arbitrary optimization problem; rather, it consists of optimizing a linear function over semidefinite and linear constraints. One general formulation of SDP is $$ \begin{align*} &\max \sum_{ij} c_{ij} x_{ij} \\ s.t. \;\;& X \succeq 0 \\ & A \mathbf{x} = \mathbf{b} \end{align*} $$ Here $X$ is the matrix whose entries ...


Only top voted, non community-wiki answers of a minimum length are eligible