id: 01901344
dt: j
an: 01901344
au: Gómez, Francisco; Hurtado, Ferran; Ramaswami, Suneeta; Sacristán, Vera;
Toussaint, Godfried
ti: Implicit convex polygons.
so: J. Math. Model. Algorithms 1, No.1, 57-85 (2002).
py: 2002
pu: Springer, Dordrecht
la: EN
cc: G.1.6 F.2 F.1.3 I.3
ut: linear constraints; linear programming; geometric object representation;
prune-and-search; complexity; computational geometry
ci:
li: doi:10.1023/A:1015626820950
ab: Summary: Convex polygons in the plane can be defined explicitly as an
ordered list of vertices, or given implicitly, for example by a list of
linear constraints. The latter representation has been considered in
several fields such as facility location, robotics and computer
graphics. In this paper, we investigate many fundamental geometric
problems for implicitly represented polygons and give simple and fast
algorithms that are easy to implement. We uncover an interesting
partition of the problems into two classes: those that exhibit an
$Ω(n\log n)$ lower bound on their complexity, and those that yield
$O(n)$ time algorithms via prune-and-search methods.
rv: