# Questions tagged [convex-hull]

The tag has no usage guidance.

42 questions
Filter by
Sorted by
Tagged with
94 views

### The optimal complexity of intersecting a line with a convex hull of a set of points in 2d

The problem: in 2d, given a line and an unordered set of $N$ points with real coordinates, find the intersection between the line and the convex hull of the points. Clearly, one can explicitly ...
• 83
1 vote
67 views

### Computing convex hull by triangle point inclusion

In my computational geometry book they present the following $O(n^4)$ algorithm for computing the convex hull of a pointset $P \subset \mathbb{R}^2$ assuming general position on the points in $P$: For ...
• 190
1 vote
47 views

### Shamos algorithm , cannot understand the Area part

I wanted to find shortest time algorithm for finding the diameter of a convex hull, so I found Shamos algorithm on wikipedia: ...
1 vote
35 views

### How can vector angle comparison between lattice points be done without using floating-points? (Convex Hull)

Let's say I have a point $(x_0, y_0)$, and some other points $(x_1, y_1), (x_2, y_2) ... (x_n, y_n)$, such that all of them are lattice points; all have integer coordinates. Let's further assume that ...
23 views

### After removing a point in the convex hull, can the remaining points construct a convex hull?

With any convex hull of n points, after delete a point from that hull, can the remaining n-1 points still construct a new convex hull? How can we prove that?
245 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 ...
• 225
1 vote
552 views

### Upper and lower tangent line to convex hull from a point

Is it possible to find an upper and lower tangent line to a convex hull in $log(n)$ time where $n$ is number of points on a convex hull? I have just done it in linear time where I checked for upper ...
• 225
155 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 ...
• 23
1 vote
157 views

### minimum number of points a convex hull must have

Quick question: Say for example there are 10 colinear points. my question is does a convex hull have to be a convex polygon? or can it be a line as well according to the formal definition of the ...
• 201
15 views

### minimum moves to be made to get out of convex hull

Given a convex hull in $XY$ plane. and we have $n$ points sitting inside it. In one move we can move all the points to right by $1$ or move all the points to up by $1$. what are the minimum number of ...
140 views

### Concentric convex hulls

Given N points in a 2D plane, if we start at a given point and start including points in a set ordered by their distance from the starting point. After including every point, we check if there is a ...
• 1
47 views

48 views

### Finidng edges of convexhull from rectangles

Green Boxes = rectangles red dots = edge points red lines = to be generated from convex hull algorithm I have a problem with creating the convex hull algorithm. I want to select or collect all the ...
51 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 ...
• 12.4k
49 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 ...
• 131
58 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, ...
• 41
2k 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 ...
69 views

• 111
895 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 ...
• 31
385 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 ...
• 247
636 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 ...
• 121
136 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 ...
18 views

### Convex Hull for known output size in O(n)

Given a set $S$ of $n$ planar points, we know that the $|CH(S)| = 17$. How can I create an algorithm that computes $CH(S)$ in $O(n)$ time? Why is it really $O(n)$?
• 129
82 views

• 493
94 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 ...
• 1,239