基于决策树模型求凸包算法下界证明.ppt

证明 显然构造的这个输入的凸包顶点集合不为前n个点 但是这个输入满足到达这个叶子的所有条件，那么它应该和其他到达这个叶子的输入一样，得到凸包为前个点的结论 矛盾！所以那个矩阵的秩必须为 引理三由此得到证明 引理四 若,那么就有 * 基于决策树模型寻找凸包算法运行时间下界的证明 证明思路 树的高度至少为 找到足够多的叶子 (张) 构造出能到达这些叶子的输入 怎么构造？？？ 证明步骤 构造出种具有特定性质的不同输入 为每种输入关联树中的一片叶子 到达这片叶子的输入具有某些特性 不同的输入不能关联同一片叶子 得到张叶子，即可证明树的高度 构造输入 构造输入 构造输入 关联叶子 选用合适的方法为每种类型的输入关联树中的一片叶子 引理一 ? 定义 刚才定理中找到的叶子就是，也就是与输入相关联的叶子 证明 利用决策树对输入集合进行划分，将其划分为有限个非空集合，每个集合对应于一片叶子 其中至少有一个集合测度不为0，因为的测度不为0 集合可以写为: 证明 考虑集合： 上面集合中的等式必须对于 是平凡的，不然会成为 中的零测集。 证明 考虑集合： 由中仅有不等式对有效 故为开集。 引理一的证明完成 思考 什么样的输入正好可以到达这片叶子？ 到达这片叶子的输入需要满足的条件究竟是什么？ 猜测 需要满足的条件中那些等式其实就是对一些三角形面积的关系的限制 也就是对于，的一些限制 引理二 设是一个次数不超过二的多项式。若有对于所有的成立，那么就有其中均为常数。 证明 把写为合适的形式 由与之对应的的性质（在一个开集上始终为0）推出中的一些系数 进一步推导出可以写为我们 想要的形式 证明 证明 证明 进一步的猜想 到达这个叶子的条件其实就是 就是那些三角形的面积都得为0才可以 引理三 对于任意的一个输入,如果到达了叶子节点,那么这个输入一定会满以下关系： 对任意的, 证明 输入要到达这个叶子需要满足的条件为： 证明 输入要到达这个叶子需要满足的条件为： 证明 输入要到达这个叶子需要满足的条件为： 记这个式子为,左边的常数矩阵 为 证明 若,则等价于 证明完成 证明 若,则等价于 我们要构造一个输入，这个输入 满足所有的这些限制条件（因此 这个输入会到达这个叶子，但是 这个输入的凸包的顶点集合却不 是前n个点，由此得到矛盾 证明思路 在原来的输入上做修改，让新输入既满足三角形的面积关系，又满足那些不等式 满足不等式只要和原来的输入距离足够近 要满足的面积关系只是一种比例 关系，控制好各三角形的面积之 比就可以了 证明 证明 证明 证明 *