TABLE OF CONTENTS We now consider the case in which 
is a set of k convex polygons with a total of n vertices. We describe a different pseudo-triangulation for 
, called the greedy vertical pseudo-triangulation, which is based on notions developed by Pocchiola and Vegter [21]. They introduced the greedy pseudo-triangulation as a tool to compute the visibility complex of a set of convex polygons. We adapt their algorithm for our collision detection application.
There are exactly four bi-tangent segments between any two disjoint convex polygons. A bi-tangent is called free if it does not intersect the interior of any object in 
. Let s and s' be two free bi-tangents with a common endpoint v, which is a vertex of a polygon 
. There are three disjoint wedges formed by the polygon edges incident upon v and between s and s'. We say that s and s' cross at v if each of these wedges spans an angle less than ?; see Figure 5. [1] We say that two free bi-tangents intersect if either they share an interior point or they have a common endpoint and they cross at that endpoint. For any linear ordering ? on the free tangents, we can build a corresponding greedy triangulation 
as follows. We first sort the tangents by ? ordering. We then scan...
