arXiv Open Access 2016

Minimizing the Total Movement for Movement to Independence Problem on a Line

Mehrdad Ghadiri Sina Yazdanbod

Lihat Sumber

Abstrak

Given a positive real value $δ$, a set $P$ of points along a line and a distance function $d$, in the movement to independence problem, we wish to move the points to new positions on the line such that for every two points $p_{i},p_{j} \in P$, we have $d(p_{i},p_{j}) \geq δ$ while minimizing the sum of movements of all points. This measure of the cost for moving the points was previously unsolved in this setting. However for different cost measures there are algorithms of $O(n \log(n))$ or of $O(n)$. We present an $O(n \log(n))$ algorithm for the points on a line and thus conclude the setting in one dimension.

Topik & Kata Kunci

cs.CG

Penulis (2)

Mehrdad Ghadiri

Sina Yazdanbod

Format Sitasi

APA MLA BibTeX

Ghadiri, M., Yazdanbod, S. (2016). Minimizing the Total Movement for Movement to Independence Problem on a Line. https://arxiv.org/abs/1606.09596

Akses Cepat

Lihat di Sumber

Informasi Jurnal

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