# Questions tagged [convex-hull]

The tag has no usage guidance.

42 questions
Filter by
Sorted by
Tagged with
1k views

### If a convex optimization problem can be NP-Hard, in what sense are convex problems easier than non-convex problems?

Being new to the OR and Optimization world, I've always assumed that a problem being convex meant that it can be solved in polynomial time. Now I am learning that a convex optimization problem can ...
530 views

### How to find the supremum over all the "good" (interior) polytopes for a given set of 3D points?

Let $S \subset \mathbf{R}^3$ be a set of points in 3D and let $O=(x_0,y_0,z_0)$ be the origin/point of reference. We consider a convex polytope $P$ good / interior if: $P$ is wholly contained ...
99 views

### $3$-dimensional convex hull using only a desired number of planes

I would like to find the convex polytope with the smallest volume that envelops (contains) all the points of a given 3D point cloud and that can be constructed from only $k$ planes. This is similar to ...
190 views

### Optimization over convex combinations in a circle

Consider the following situation: given a triangle $ABC$ inscribed in a circle, define $f$ as the product $$f(P) = d(P, A) \; d(P,B) \; d(P,C)$$ where $P$ is a point on the circle and $d$ are ...
1k views

### Convex-hull of a star shaped polygon in O(n)

I'm trying to develop an algorithm to find a convex hull of a star shaped polygon in $O(n)$ time. The specific problem, which is also described here, is as follows: A polygon $P$ is star-shaped if ...
49 views

### Minimal set of inequalities including good points but excluding bad points

Suppose I have a collection of good convex sets and bad convex sets in $\mathbb{R}^d$ (where $d$ can be big). Each convex set is defined by a series of closed ranges in each dimension $d$ - a ...
53 views

### Convex hull in a discrete space

I know some algorithms which compute the convex hull in a continuous space. Are there efficient algorithms to compute it in a discrete domain? For example in 3D discrete space, given the blue points, ...
113 views

### Difference between convex hull algorithms

I was wondering what are the main differences in terms of efficiency of convex hull algorithms? Brute force algorithm is inefficient due to iterating over every three vertices in our set and its time ...
398 views

### Convex hull algorithm in $O(\min(mn, n\log n))$

I am looking for an algorithm to compute the convex hull of a set of $n$ points $P$. The hull should contains $m$ points. This algorithm should work in time $O(\min(mn,n \log n))$. My first guess was ...
93 views

### How to use convex hull for this problem

Problem: You are to collect a total of $N$ litres of red and $M$ litres of blue liquid. For doing job $i$ for time $t$, you get $a_i t$ litres of red and $b_i t$ litres of blue liquid. $t$ need not ...
342 views

### Is binary-search really required in Chan's convex hull algorithm?

I have a little doubt about Chan's algorithm. From Wikipedia's description we see that the second phase of an algorithm works with $K = \mathrm{ceil}(\frac{n}{m})$ subsets $Q_i$. The goal of the ...
127 views

### Why is the graph inside Graham Scan always planar

One of the ways to prove that Graham Scan constructs convex hull in linear time is using planarity of the graph obtained by running the algorithm. This graph is always planar, so according to Euler's ...
44 views

### Distance from high dimensional convex hull to target point T

I have a set S of high dimensional points in Euclidean space, with convex hull H (not known); and some target point T in that space not in or on H. Rather than worry about calculating both H and the ...
818 views

### 3D gift wrapping algorithm: how to find the first face in the convex hull?

I am implementing the gift wrapping algorithm to find the convex hull of a set of points in the 3D space. However, all the articles I have read seem to omit the description of the first step of the ...
949 views

### The use of binary search when determining whether a point lies inside a given convex hull

In an answer to the problem of determining whether or not a point lies inside a given convex hull, a thesis is mentioned, which says : For repeated queries with preprocessing allowed, we develop a ...
107 views

### Maximize length of side of triangle from points on a circle

Given a circle with $n$ points, among all triangles we can make using these points, we want to find a triangle with maximum length of its shortest side in $o(n^2)$. We try to make a relation between ...
128 views

### Efficient algorithm to compute the diameter of a convex set?

Is there a polynomial algorithm that can compute the diameter (the distance between the furthest points) of a convex set? It is possible to do it efficiently for a set of points, but imagine that the ...
73 views

590 views

### Minimum distance between two convex hulls maximized

I want to implement a program that splits a set $S$ of $n$ points in the plane into two sets such that the distance of the convex hulls of the two sets is maximized. It should be done in $O(n^3)$. I ...
228 views

191 views

### Nested Convex Hulls Algorithm

The convex hull of a point set is a well understood problem and nice optimal solutions are known in the case of a finite point set and a simple polygon. For a convex polygon, the hull is the polygon ...
725 views

### Finding the Convex Layers of a given set of points

Definition of convex layers can be found at wikipedia. I was trying to understand this algorithm , which works in O(n log n) time, which is optimal. In the paper, the author has described two ...
47 views

### Does Optimal Substructure implies Convexity and vice versa?

In undergraduate CS, Dynamic Programming problems are often related to Overlapping Optimal Substructure (https://en.wikipedia.org/wiki/Optimal_substructure). Dynamic Programming is also often used in ...
385 views

170 views

### Convex Hull Problem proof [closed]

In a given set of points, Prove that the two farthest points are the vertices of the convex hull, How can i get the accurate proof, so that the question can be explained in the class