Fast Algorithms to Partition Simple Rectilinear Polygons | Zendy

San-Yuan Wu | Zendy; Sartaj Sahni | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Fast Algorithms to Partition Simple Rectilinear Polygons

Author(s) -

San-Yuan Wu,

Sartaj Sahni

Publication year - 1990

Publication title -

vlsi design

Language(s) - English

Resource type - Journals

eISSN - 1065-514X

pISSN - 1026-7123

DOI - 10.1155/1994/16075

Subject(s) - polygon (computer graphics) , partition (number theory) , rectilinear polygon , star shaped polygon , algorithm , point in polygon , mathematics , combinatorics , simple (philosophy) , simple polygon , polygon covering , regular polygon , computer science , geometry , convex set , telecommunications , philosophy , epistemology , convex optimization , frame (networking)

Two algorithms to partition hole-free rectilinear polygons are developed. One has complexity ∼ O(kn) and theother O(n log k) where n is the number of vertices in the polygon and k is the smaller of the number of verticaland horizontal inversions of the polygon, k is a measure of the simplicity of a polygon. Since k is small for mostpractical polygons, our algorithms are fast in practice. Experimental results comparing our algorithms with thatof Imai and Asano [1] are also presented

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research