Polygonalization and Trapezoidalization

[Amber Agrawal]

Q1. Can anybody give me some algorithm or pointer to a algorithm
    for Trapezoidalization of a generic polygon?
 
Q1.1 Is there any algorithm, which gives the minimum number of
     axis parallel trapezoid as a output of the Trapezoidalization
     of a generic polygon?
 
Q2. Can anybody give me some good algorithm or pointer to algorithm
    for Polygonalization of axis parallel trapezoids?
 
One trivial solution for Q2 is same as input (Viz. set of input
axis parallel trapezoid), because each trapezoid in nothing but
generic polygon. But, I want to minimize the number of generic
polygon,
 
 
Terminology used in above questions:
 
   Trapezoidalization: Decomposing the generic polygon into
                       axis-parallel trapezoids.
   Polygonalization: Given the set of non-overlapping axis-parallel
                     trapezoids, generate the set of non-overlapping
                     generic polygon such that both (set of input
                     non-overlapping axis-parallel trapezoids and set of
                     output non-overlapping generic polygon) cover the
                     same area in 2D plan.
   Generic Polygon: It(polygon) may be self-intersecting and also may
                    have holes in it.
   Axis Parallel Trapezoid : Two edges of the trapezoid are parallel to
                             x-axis or y-axis.                      

thanks,
Amber Agrawal.


Get 250 color business cards for FREE!
http://businesscards.lycos.com/vp/fastpath/

-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.