6.Geometric Intersection (几何求交）- Preliminary

1.Introduction

难度由易到难

• 判断是否有交点
  • 交点个数
• 枚举交点
• 构造交际部分的几何物体

2.EU

Element Uniqueness(EU)： 元素归一性

如何判断下面是否存在重复的元素？

解决方法

首先进行排序

EU算法的主要消耗时间是在预处理,也就是排序上面

3.MIN-Gap

通过规约的方法，可以算出算法复杂度。

• EU 问题和 Min-Gap 的输入都是 n 个整数
• Min-Gap 的每一个输出也应该准换位  EU 问题的答案，EU 问题的答案就是所有元素互不相同，当且仅当 Min-gap 是一个正数。

4.Max-Gap

通过hash算法存储元素，然后再扫描hash table就可以得到最大值

5.IEU

IEU是EU的一个变种，IEU只考虑整数的情况