Covering points with convex sets of minimum size
| Autor: | Noushin Saeedi, Sang Won Bae, William S. Evans, Chan-Su Shin, Hwan-Gue Cho |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Convex hull
General Computer Science Regular polygon Convex set 0102 computer and information sciences 02 engineering and technology 01 natural sciences Theoretical Computer Science Combinatorics Perimeter Cover (topology) 010201 computation theory & mathematics TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Bounded function 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Convex combination Orthogonal convex hull Mathematics |
| Zdroj: | Theoretical Computer Science. 718:14-23 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2016.11.014 |
| Popis: | For a set P of n points in the plane, we present algorithms for finding two bounded convex sets that cover P such that the total area or perimeter of the convex sets is minimized in O ( n 4 log n ) and O ( n 2 log n ) time, respectively. The former is the first result for minimum total area, and the latter is an improvement on the fastest previous algorithm for minimum total perimeter, which runs in O ( n 3 ) time [24] . We also extend our algorithms to find k ⩾ 2 convex sets minimizing area in O ( n 2 k ( k − 1 ) log n ) time. The algorithms can be applied to detect road intersections from the GPS trajectories of moving vehicles for automated map generation or partial clustering. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect