Combinatorial Algorithms for Finding Enclosed Empty Regions and Set Operations on Polygons

Abstract

This thesis studies interesting problems in the area of geometry related to polygonssuchasfindingthemaximumarearectangle,findingthemaximum area annulus, performing set operations on polygons, and generating random curves inside any digital object.It proposes algorithms for the same alongwiththeirpotentialapplicability.Foralltheproblemsaddressedhere, we have assumed an underlying isothetic grid.Isothetic grids are formed by the intersection of vertical and horizontal line segments i.e.,segments parallel to the coordinate axes.This thesis is divided into two primary sections.Thefirstsectionpertainstoidentifyingenclosedareas,includingthe largestemptyrectanglesandthemaximumemptyannulus,amidstvarious obstructions.Thelatterpartpertainstoperformingdifferentsetoperations onpolygonsandemphasizesthepracticalimplementationofthepolygonal structure.The interval tree data structure is used to find the largest empty rectangle.The algorithm runs in O(r nlogn)time, where n is the number of line segments and r is the number of candidate empty rectangles for a line segment.Annulus is the region between two rectangles, one of which enclosestheother,thespacebetweenthetworectanglesisknownasthearea oftheannulus.Wepresentalgorithmstofindannulusfromasetofisothetic linesegmentsusinganintervaltreeandalistdatastructure,andfromaset of points by storing the points in a binary search tree data structure.The computationtimeforthe algorithms is O(k nlogn), where k is the number ofcandidateannulusandn isthenumberoflinesegments,andO(mlogm), wheremisthenumberofpointsrespectively.Inthesecondpartofthethesis, wehavedesignedalgorithmstoperformsetoperationsonpolygonsandalso proposedanalgorithmtogeneratearandomcurvewithintheinnerisotheticcover (IIC)of a digital image.The first step in carrying out the various set operationsonpolygons,suchasunion,intersection,andsetdifference,isto locatethepointsofintersectionbetweenthepolygons. Thetimerequiredto findthepointsofintersectionisO(nlogn),wherenisthenumberofline newlinesegmentsofthepolygons.Afterthepointsofintersec