Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [convex-hull]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
18 views

Algorithms for unordered vertices of the convex hull

For the sake of this question a "non-ordering" "set of vertices of convex hull" algorithm produces the collection of all points on the convex hull of its input without producing ...
worldsmithhelper's user avatar
0 votes
0 answers
16 views

Algorithm for surface mesh of convex decomposition

I have an object mesh. This is loaded into a physics simulator, which does a convex decomposition. Now I want to perform operations outside the simulator that require a mesh representation. I could ...
Johannes's user avatar
2 votes
0 answers
32 views

On a set of points uniformly distributed in a circle, on average, what would be better? Graham's scan or Jarvis's march

I got this question in an exam and my approach was to use probability. Jarvis's march is better than Graham's scan if h < log(n) So I calculated the probability of a point being on the circle ...
Saad Ahmed's user avatar
0 votes
0 answers
26 views

Detailed exposition for proof of Localization Lemma in paper "Random Walks in a Convex Body and an Improved Volume Algorithm"

I've begun reading the paper "Random Walks in a Convex Body and an Improved Volume Algorithm" by Lovász-Simonovits ('93). Although the paper for the most part is pretty self-contained and ...
total dependent random choice's user avatar
2 votes
1 answer
119 views

Computing an initial ellipsoid for solving a convex program

Suppose we want to find a vector $x\in R^n$ that satisfies the constraints $g_i(x)\leq 0$, for $i\in 1,\ldots, m$, where all $g_i$ are convex functions. The functions can be given by an oracle access: ...
Erel Segal-Halevi's user avatar
0 votes
1 answer
60 views

Quickhull vs T.M. Chan vs Avis and Fukuda

From Discrete lizard's answer and Handbook of Computational Geometry (Third edition, 2018) Section 26, Chazelle's solution of high dimensional convex hull achieved worst case optimal. T.M. Chan's ...
ShoutOutAndCalculate's user avatar
0 votes
0 answers
17 views

From the boundary description to the lattice description of the David Avis & Komei Fukuda's convex hull algorithm

This is a continued question from: The updated convex hull algorithms in 2023? From Handbook of Computational Geometry (Third edition, 2018) section 26.3, Seidel mentioned the boundary and the lattice ...
ShoutOutAndCalculate's user avatar
2 votes
1 answer
86 views

The updated convex hull algorithms in 2023?

I'm studying the convex hull algorithms in the high dimensions. There were two papers by Bernard Chazelle and T.M. Chan from the 90s, to have achieved the at then the state of the art complexity. ...
ShoutOutAndCalculate's user avatar
0 votes
0 answers
19 views

Implementation of algorithm to enumerate all vertices of a convex polyhedron defined as linear inequalities?

I am looking for an implementation for any of the methods to enumerate all vertices of a convex polyhedron defined by $Ax \leq b$ I have found some papers that talk about the problem, for example this ...
Makogan's user avatar
  • 341
2 votes
1 answer
71 views

Collinear convex hull

Is there an algorithm where I provide a list of non-overlapping squares, for example: ...
user17952421's user avatar
0 votes
1 answer
182 views

Graham's scan algorithm including all colinear points

I'm solving the Erect the Fence problem on leetcode. My approach is to use Graham's scan algorithm with the following steps: Find the leftmost point p0 Sort the points according to their angle ...
Karol Borkowski's user avatar
2 votes
0 answers
26 views

Topologizing boundaries in 3D space

I have a set of closed curves (not convex, not planar) in 3D. The goal is to produce A mesh (any will do) that is manifold and contains the closed curves as boundaries/holes. For example like this ...
Makogan's user avatar
  • 341
0 votes
1 answer
33 views

Compute upper convex hull of a function surface

I have a sampled function sruface $$ z = f(x, y) $$ represented as a grayscale raster image. How to find the upper convex hull of that surface. That is I am looking for the minimal $$ g(x, y) $$ such ...
user877329's user avatar
2 votes
2 answers
149 views

Why isn't there a computational "Carpenter's Algorithm" for Planar Convex Hull?

Planar Convex Hull is a problem where you have $N$ points in a Cartesian plane, and you want to find the smallest convex polygon that encloses the points. QuickHull seems to be the best available ...
Visipi's user avatar
  • 23
1 vote
2 answers
225 views

What is the optimal algorithm for merging an arbitrary number of convex hulls?

Preparata & Shamos in "Convex Hulls: Basic Algorithms" (1985), give a linear algorithm for merging two convex hulls in $O(n+m)$ time, where $n$ and $m$ are the numbers of vertices in ...
Logan R. Kearsley's user avatar
5 votes
2 answers
173 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 ...
hidanom's user avatar
  • 83
1 vote
2 answers
126 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 ...
sn3jd3r's user avatar
  • 190
2 votes
1 answer
200 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: ...
Nameless's user avatar
  • 173
0 votes
1 answer
64 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 ...
Christopher Miller's user avatar
3 votes
1 answer
1k 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 ...
Exzone's user avatar
  • 235
1 vote
1 answer
2k 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 ...
Exzone's user avatar
  • 235
2 votes
1 answer
258 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 ...
amos's user avatar
  • 23
2 votes
1 answer
437 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 ...
Sid's user avatar
  • 211
0 votes
0 answers
17 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 ...
White Knife's user avatar
-1 votes
2 answers
156 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 ...
Anon's user avatar
  • 1
0 votes
0 answers
181 views

Why are basic feasible solutions the same as vertices geometrically?

The first line on the Wikipedia page for basic feasible solutions reads, ...
Legolas's user avatar
0 votes
1 answer
56 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 ...
Enniyan's user avatar
4 votes
0 answers
53 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 ...
orlp's user avatar
  • 13.6k
3 votes
0 answers
51 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 ...
jdowdell's user avatar
  • 131
4 votes
0 answers
71 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, ...
Smith's user avatar
  • 41
9 votes
2 answers
3k 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 ...
Sasha the Noob's user avatar
2 votes
1 answer
111 views

Determine image of hypercube under linear map

Let $A$ be an $3\times N$ matrix (where $N$ is large) with nonnegative real entries. I'd like an algorithm for determining when a vector $v\in\Bbb R^3$ can be written as $Aw$ for some vector $w\in\Bbb ...
Oscar Cunningham's user avatar
1 vote
0 answers
98 views

Game Theory: Using a convex hull algorithm to map out Pareto outcomes

I have started studying the Pareto efficiency notion in Game theory. The definition I am familiar with is this: Strategy profile $\mathbf{s}$ Pareto dominates strategy $\mathbf{s}'$ if for all $i\in\...
johnny09's user avatar
  • 111
4 votes
2 answers
1k 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 ...
shdown's user avatar
  • 41
3 votes
1 answer
561 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 ...
Y N's user avatar
  • 247
2 votes
1 answer
734 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 ...
Strahinja's user avatar
  • 121
3 votes
1 answer
146 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 ...
Venus's user avatar
  • 151
0 votes
0 answers
20 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)$?
GeomForFun's user avatar
2 votes
1 answer
88 views

Lower bound for point set triangulation

How can I show that the lower bound for getting a triangulation from a point set in the plane is $\Omega(n \log n)$? I know that the lower bound for finding the convex hull for a point set is also $\...
Chypsylon's user avatar
1 vote
1 answer
329 views

How to prove that non-antipodal vertices cannot be a diameter of a convex polygon?

I am learning Shamos's rotating calipers algorithm for finding the diameter of a convex polygon in his Ph.D. thesis; Page 78. It reads Consult Figure 3.23 and notice that parallel lines of support ...
hengxin's user avatar
  • 9,561
1 vote
1 answer
190 views

Convex hull of fixed size

I have heard that the quickhull algorithm can be modified if the size of the convex hull (the number of points it consists of) is known beforehand, in which case it will run in linear time. What ...
IS4's user avatar
  • 167
7 votes
1 answer
629 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 ...
0x90's user avatar
  • 259
1 vote
0 answers
245 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 ...
user avatar
2 votes
1 answer
1k 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 ...
Bruno Vandekerkhove's user avatar
1 vote
1 answer
103 views

How to convert two conflicting objective functions into a single objective function

I have two objective functions say f1 where I have to minimize (X+Y) and another function f2 where I have to maximize (A-B). The two functions are conflicting. I need to convert them into a ...
user2567806's user avatar
2 votes
1 answer
195 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,...
phipsgabler's user avatar
1 vote
0 answers
782 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 ...
Mooncrater's user avatar
4 votes
1 answer
2k 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 ...
user avatar
5 votes
1 answer
239 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 ...
Drew's user avatar
  • 51
6 votes
0 answers
116 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 ...
balt's user avatar
  • 61