Implicit Convex Polygons

Francisco Gómez, Ferran Hurtado, Suneeta Ramaswami, Vera Sacristán, Godfried Toussaint

Research output: Contribution to journalArticlepeer-review


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 Ω(nlog n) lower bound on their complexity, and those that yield O(n) time algorithms via prune-and-search methods.

Original languageEnglish (US)
Pages (from-to)57-85
Number of pages29
JournalJournal of Mathematical Modelling and Algorithms
Issue number1
StatePublished - 2002


  • complexity
  • computational geometry
  • geometric object representation
  • linear constraints
  • linear programming
  • prune-and-search

ASJC Scopus subject areas

  • Modeling and Simulation
  • Applied Mathematics


Dive into the research topics of 'Implicit Convex Polygons'. Together they form a unique fingerprint.

Cite this