Name
Abstract | ||
|---|---|---|
In recent years, more and more algorithms related to imprecise data have been proposed. Specifically, some algorithms on computing the maximum area convex hull are designed recently when the imprecise data are modeled as non-overlapping axis-aligned squares or as equal size squares. The time complexity of the best known algorithm based on non-overlapping axis-aligned squares is O(n7). If the squares have equal size and can overlap, the time complexity of the best known algorithm is O(n5). In this paper, we improve the former from O(n7) to O(n5) and improve the latter from O(n5) to O(n2). These results are obtained by exploiting the non-trivial geometric properties of the problems. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s10878-012-9488-5 | J. Comb. Optim. |
Keywords | Field | DocType |
Imprecise data,Computational geometry,Convex hull | Mathematical optimization,Combinatorics,Computational geometry,Convex hull,Time complexity,Output-sensitive algorithm,Mathematics | Journal |
Volume | Issue | ISSN |
26 | 4 | 1382-6905 |
Citations | PageRank | References |
2 | 0.37 | 8 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wenqi Ju | 1 | 19 | 3.24 |
| Jun Luo | 2 | 222 | 26.61 |
| Binhai Zhu | 3 | 903 | 109.96 |
| Ovidiu Daescu | 4 | 276 | 45.78 |