Výpočet konvexného obalu obnáša zostrojenie jednoznačnej a efektívnej reprezentácie požadovaného konvexného útvaru.
[[Výpočtová zložitosť|Zložitosť]] jednotlivých algoritmov je zvyčajne odhadovaná v závislosti od '''<math>n'''</math>, čiže počtu vstupných bodov, a '''<math>h'''</math>, čiže počtu výstupných bodov, tj. počet bodov tvoriacich konvexný obal.
Pre body v 2D a 3D existujú algoritmy pracujúce s časovou zložitosťou <math>O(n \log h)</math>. Pre dimenzie '''<math>d'''>3 vyššie ako 3</math> poznáme algoritmy, ktorých časová zložitosť je rovná <math>O(n^{\lfloor d/2\rfloor})</math>, co je zároveň aj optimálne riešenie tohoto problému.<ref>{{Citácia periodika|priezvisko=Chazelle|meno=Bernard|titul=An optimal convex hull algorithm in any fixed dimension|periodikum=Discrete & Computational Geometry|dátum=1993-12-01|ročník=10|číslo=4|strany=377–409|issn=0179-5376|doi=10.1007/bf02573985|url=https://link.springer.com/article/10.1007/BF02573985|dátum prístupu=2018-02-19|jazyk=en}}</ref>
