# Questions tagged [convex-hull]

The tag has no usage guidance.

26 questions
Filter by
Sorted by
Tagged with
435 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 ...
92 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 ...
139 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 ...
635 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 ...
224 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 ...
89 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 ...
144 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 ...
64 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 ...
483 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 ...
56 views

274 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 ...
93 views

### Internal tangent intersection of two point sets in linear time

I need to find the intersection of the internal tangents of two point sets $V_a, V_b$ in $\mathbb{R}^2$, defined via their convex hulls. We can assume that the sets are disjoint and linearly separable,...
124 views

116 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 ...
37 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 ...
369 views