arXiv Open Access 2016

Faster Bottleneck Non-crossing Matchings of Points in Convex Position

Marko Savić Miloš Stojaković

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.CG

Penulis (2)

Marko Savić

Miloš Stojaković

Format Sitasi

APA MLA BibTeX

Savić, M., Stojaković, M. (2016). Faster Bottleneck Non-crossing Matchings of Points in Convex Position. https://arxiv.org/abs/1602.04922

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2016
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓