Test Report - Rectilinear Polygon Resizing

Platform: Sun Ultra 5, 333Mhz, 256M RAM

1. All programs pass the DEFAULT two testcases.

2. The following is the results tested by 13 NEW testcases:

Case#	Points#	Test		A01	A02	A04	A42
case3	8	Correct:	Yes	Yes	Fail	Yes
		Time:		<1s	<1s	<1s	<1s
		
case4	14	Correct: 	No	Yes	Yes	Yes
		Time:		<1s	<1s	<1s	<1s

case5	24	Correct:	Yes	Yes	Yes	Yes
		Time:		<1s	<1s	<1s	<1s

case6	86	Correct:	N/A	Yes	Yes	Yes
		Time:		>2h	2.6s	<1s	<1s

case7	126	Correct:	N/A	Yes	Yes	Yes	
		Time:		>2h	8s	<1s	<1s

case8	122	Correct:	N/A	No	Yes	Yes
		Time:		>2h	21s	<1s	<1s

case9	146	Correct:	No	Yes	Yes	Yes
		Time:		<1s	14s	<1s	<1s

case10	2312	Correct:	SegV	SegV	SegV	Yes
		Time:		<1s	4s	<1s	29s
		Memory:					203M

case11	2768	Correct:	SegV	Yes	Yes	Yes
		Time:		<1s	17m12s	2s	35s
		Memory:			1.2M	1.5M	36M

case12	9236	Correct:	N/A	SegV	Yes	SegV
		Time:		N/A	47h	26s	8m
		Memory:				2.3M		

case13	20636	Correct:	N/A	SegV	Yes	SegV	
		Time:		N/A	3h	56s	116s
		Memory:				3.3M	20M	

case14	57268	Correct:	N/A	N/A	Fail	SegV	
		Time:		N/A	>13h	118s	57s
		Memory:				7.7M	3.7M	

case15	103802	Correct:	N/A	N/A	Yes	SegV	
		Time:		N/A	N/A	11s	45s
		Memory:				11M	16M	


3. Algorithm:

A01: (i). trapzoidalization + finding edge visible pairs
     (ii). use shrinking to do growing

A02: Brute force incremental resizing algorithm by moving a very 
     small step each time.

A04: Incremental resizing algorithm by moving a critical distance
     each time.

A42: (i) trapzoidalization + growing each rectangle + merging
     (ii) using growing to do shrinking

4. Comments:

(i). A04 and A42 have better results.  Both algorithms of A04 and
     A42 are correct.  A42 realizes a special property when only
     rectilinear polygons are considered to resizing and provides 
     a different clever algorithm.

(ii). A04 has the best performance and only A04 passes the 
     large testcases: case12, case13 and case15.  But A04 may 
     fail by assertion or segv for some testcases.

(iii). My recommendation is A04 > A42 > A02 > A01