Computing the center region and its variants
SCIE
SCOPUS
- Title
- Computing the center region and its variants
- Authors
- Oh, E.; AHN, HEE KAP
- Date Issued
- 2017-03
- Publisher
- Springer Verlag
- Abstract
- We present an O(n2 log4 n)-time algorithm for computing the center region of a set of n points in the three-dimensional Euclidean space. This improves the previously best known algorithm by Agarwal, Sharir and Welzl, which takes O(n2+��) time for any �� > 0. It is known that the complexity of the center region is ��(n2), thus our algorithm is almost tight. The second problem we consider is computing a colored version of the center region in the two-dimensional Euclidean space. We present an O(n log4 n)-time algorithm for this problem. ? Springer International Publishing AG 2017.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/107801
- DOI
- 10.1007/978-3-319-53925-6_20
- ISSN
- 0302-9743
- Article Type
- Article
- Citation
- Lecture Notes in Computer Science, vol. 10167 LNCS, page. 254 - 265, 2017-03
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.