5

If $n$ is the number of 2D points, let $h \le n$ be the number of points on the convex hull. Then: Gift wrapping takes time $\Theta(n h)$, which can be $\Theta(n^2)$ in the worst case. It is relatively simple to implement. Gift-wrapping generalizes to 3 dimensions and beyond. Graham scan takes time $O(n \log n)$. It is very easy to implement especially if ...


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}$ ...


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

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,...


3

You could transform the question into finding the biggest minimum angle of the triangle vertices relative to the centre. Preparatory work: Find centre $(x_C, y_C)$, if not already known (intersect bisectors of randomly-chosen pairs of points). $o(1)$ a) Make list of angle position for each point, $a_i = \text{atan2}(y_i-y_C, x_i-x_C)$. $o(n)$ b) Sort angle ...


3

I suspect that if the points in your set are expressed as $Ax \le b$ and you're considering the Euclidean distance, then you can solve the following quadratic program with the ellipsoid method: $$ \max \sum_i (x^2_i+y^2_i-2x_i y_i) \\ Ax \le b \\ Ay \le b. $$ Where we used the fact that optimizing $|x-y|$ is the same as optimizing $ \frac{1}{2} |x-y|^2 = \...


3

The convex hull of 10 collinear points is the line segment between the two extreme points. No, a convex hull does not have to be convex polygon. A convex hull can be a point, a line segment, a ray, a line, a convex polygon, a circular sector, a half plane, a cubic, etc. . A definition in math, such as the definition of convex hull, is the strictest kind of ...


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

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 $...


2

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, ...


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

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 ...


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

Let's assume that the convex polygon $P$ is defined as an ordered list $(p_0,p_1,...,p_{n-1})$ of points, and for each such point $p \in P$ we are able in $O(1)$ time to find a previous point $Prev(p)$ and a next point $Next(p)$ according to this order, taking into account that: $$Prev(p_0)=p_{n-1}$$ $$Next(p_{n-1})=p_0$$ The binary search over this list is ...


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 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

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

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'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

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