假没Q包含k个非空的最大居,并设y;是L;中最左边点的y坐标(i=1, 2,..., k)。假定Q中没有丙个点有相同的x坐标或y坐标。
a.证明
。考虑一个点(x, y),它在Q中任意点的左边,并且其y坐标与Q中任何点的y坐标都不相同。设Q'=QU((x, y)}。
b.设j是满足yi<y的最小下标，除非y<yk,在这种情况下，令j=k+1。
证明Q的最大层如下:
d.如果允许输入点有相同的x坐标或y坐标，会不会出现问题?如果会，提出一种方法来解决这一 问题。
- 若j≤k,则Q的最大层与Q的最大层相同，只是Lj也包含(x, y) 作为其新的最左点。
- 若j=k+1,则Q’的前k个最大层与Q的相同，但此外，Q'有一个非空的第k+1最大层Lk+1={(x, y)}。
d.如果允许输入点有相同的x坐标或y坐标，会不会出现问题?如果会，提出一种方法来解决这一 问题。
