Please use this identifier to cite or link to this item:
https://open.uns.ac.rs/handle/123456789/2907
Title: | Faster bottleneck non-crossing matchings of points in convex position | Authors: | Savić, Mirko Stojaković, Mila |
Issue Date: | 1-Oct-2017 | Journal: | Computational Geometry: Theory and Applications | Abstract: | © 2017 Elsevier B.V. Given an even number of points in a plane, we are interested in matching all the points by straight line segments so that the segments do not cross. Bottleneck matching is a matching that minimizes the length of the longest segment. For points in convex position, we present a quadratic-time algorithm for finding a bottleneck non-crossing matching, improving upon the best previously known algorithm of cubic time complexity. | URI: | https://open.uns.ac.rs/handle/123456789/2907 | ISSN: | 09257721 | DOI: | 10.1016/j.comgeo.2017.05.002 |
Appears in Collections: | FTN Publikacije/Publications |
Show full item record
SCOPUSTM
Citations
2
checked on Jul 8, 2023
Page view(s)
2
Last Week
1
1
Last month
0
0
checked on May 10, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.