##
Convex Hulls of Algebraic Curves

####
David J. Kriegman, Erliang Yeh, and Jean Ponce

###
Abstract

A new algorithm based on curve tracing and decomposition techniques is
presented for computing the convex hull of an algebraic curve defined
implicitly by f(x,y)=0; the curve may have multiple components as
well as singular points. The output is an ordered collection of line
segments and sections of the curve represented by a sample point and
interval bounds; this representation is suitable for rendering the
convex hull by classical curve tracing techniques. Additionally, we present a
point classification function for the convex hull based on Sturm
sequences. Progress toward extending these results to algebraic
surfaces is briefly discussed.