An O(n log n)-Time Algorithm for the Restricted Scaffold Assignment

Simple item page
dc.creatorColannino, Justin
dc.creatorDamian, Mirela
dc.creatorHurtado, Ferran
dc.creatorIacono, John
dc.creatorMeijer, Henk
dc.creatorRamaswami, Suneeta
dc.creatorToussaint, Godfried
dc.date2005-07-05
dc.date2005-07-05
dc.date.accessioned2026-07-07T03:23:12Z
dc.date.available2026-07-07T03:23:12Z
dc.descriptionThe assignment problem takes as input two finite point sets S and T and establishes a correspondence between points in S and points in T, such that each point in S maps to exactly one point in T, and each point in T maps to at least one point in S. In this paper we show that this problem has an O(n log n)-time solution, provided that the points in S and T are restricted to lie on a line (linear time, if S and T are presorted).
dc.description13 pages, 8 figures
dc.identifierhttps://arxiv.org/abs/cs/0507013
dc.identifierhttp://arxiv.org/abs/cs/0507013
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/32851
dc.subjectComputational Geometry
dc.subjectDiscrete Mathematics
dc.subjectF.2.2; G.2.2
dc.titleAn O(n log n)-Time Algorithm for the Restricted Scaffold Assignment
dc.typetext

Files

Collections

arXiv