سوال ۵۶ کنکور ارشد مهندسی کامپیوتر ۱۴۰۲

The convex hull of $n$ points in the plane can be computed in $\Theta(n\log n)$ time, and this is optimal in the comparison model.

Upper bound — an $O(n\log n)$ algorithm exists. Classic algorithms achieve this bound:

• Graham scan: sort the points by polar angle (or by $x$-coordinate, as in Andrew's monotone chain), then sweep once maintaining a stack and discarding non-left-turn vertices. Sorting costs $\Theta(n\log n)$; the linear scan costs $\Theta(n)$. Total: $\Theta(n\log n)$.

Lower bound — $\Omega(n\log n)$ is unavoidable. Computing the hull is at least as hard as sorting: given numbers $x_1,\dots,x_n$, lift each to the parabola point $(x_i, x_i^{2})$. All these points are in convex position, so the convex hull, read along its boundary, returns them in sorted $x$-order. A hull algorithm faster than $\Omega(n\log n)$ would sort faster than the comparison-sorting lower bound allows — a contradiction. Hence $\Omega(n\log n)\ \le\ \text{(convex hull)}\ \le\ O(n\log n)\ \Rightarrow\ \Theta(n\log n).$

Eliminating the other options.

So the best possible (optimal) algorithm runs in $\Theta(n\log n)$, option 3.

Exam trick: Convex hull is one of the canonical problems whose lower bound is proved by reduction from sorting (lift to a parabola). Whenever an exam asks for the "best possible" hull time, the answer is $\Theta(n\log n)$ — unless it explicitly asks for an output-sensitive bound, in which case Chan's algorithm gives $\Theta(n\log h)$ with $h$ = number of hull vertices.