Name
Abstract | ||
|---|---|---|
Data collected from real world are often imprecise. A few algorithms were proposed recently to compute the convex hull of maximum area when the axis-aligned squares model is used to represent imprecise input data. If squares are non-overlapping and of different sizes, the time complexity of the best known algorithm is O(n7). If squares are allowed to overlap but have the same size, the time complexity of the best known algorithm is O(n5). In this paper, we improve both bounds by a quadratic factor, i.e., to O(n5) and O(n3), respectively. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-22685-4_17 | COCOON |
Keywords | Field | DocType |
convex hull,imprecise input data,maximum area,largest area convex hull,known algorithm,real world,axis-aligned squares model,quadratic factor,imprecise data,different size,time complexity | Extreme point,Discrete mathematics,Combinatorics,Quadratic equation,Convex hull,Non-linear least squares,Simple polygon,Time complexity,Output-sensitive algorithm,Mathematics | Conference |
Citations | PageRank | References |
0 | 0.34 | 15 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ovidiu Daescu | 1 | 276 | 45.78 |
| Wenqi Ju | 2 | 19 | 3.24 |
| Jun Luo | 3 | 222 | 26.61 |
| Binhai Zhu | 4 | 903 | 109.96 |