X hits on this document

Powerpoint document

Finding the Largest Area Axis-Parallel Rectangle in a Polygon in O(n log2 n) Time - page 17 / 26

58 views

0 shares

0 downloads

0 comments

17 / 26

A General Framework for the 2-Contact Case

P

Property I

Polygonal regions P and P’ satisfy P’   P and each vertex-edge rectangle for P, V, and E is a vertex-edge rectangle for P’, V’, and E’.

Property II

For every vertex v V’ and every edge e E’: if any point q interior(e) is rectangularly visible from v inside P’, then all of e is rectangularly visible from v.

Property III

If vertex v V’ and a point q E’ are rectangularly visible with respect to vertices(P’), then v and q are rectangularly visible with respect to P’.

V

E

P’

V’

E’

Given vertically separated, y-monotone chains V, E of P, “orthogonalize” them

Goal: reduce to the Largest Empty Corner Rectangle (LECR) problem

Document info
Document views58
Page views59
Page last viewedMon Dec 05 14:07:58 UTC 2016
Pages26
Paragraphs355
Words1367

Comments