Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/14505

Connect the dot: computing feed-links for network extension
Speckmann, Bettina; Silveira, Rodrigo Ignacio; Aronov, Boris; Buchin, Kevin; Buchin, Maike; Jansen, Bart; De Jong, Tom; Kreveld, Marc van; Loffler, Maarten; Luo, Jun
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada II; Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta
Road network analysis can require distance from points that are not on the network themselves. We study the algorithmic problem of connecting a point inside a face (region) of the road network to its boundary while minimizing the detour factor of that point to any point on the boundary of the face. We show that the optimal single connection (feed-link) can be computed in O(λ7(n) log n) time, where n is the number of vertices that bounds the face and λ7(n) is the slightly superlinear maximum length of a Davenport- Schinzel sequence of order 7 on n symbols. We also present approximation results for placing more feed-links, deal with the case that there are obstacles in the face of the road network that contains the point to be connected, and present various related results.
Peer Reviewed
Àrees temàtiques de la UPC::Matemàtiques i estadística::Geometria::Geometria algebraica
Àrees temàtiques de la UPC::Matemàtiques i estadística::Investigació operativa::Optimització
Geometry, Algebraic
Operations research
Management science
Geometria algèbrica
Optimització i investigació operativa
14Q Computational aspects in algebraic geometry
90B Operations research and management science
Attribution-NonCommercial-NoDerivs 3.0 Spain
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
info:eu-repo/semantics/publishedVersion
Artículo
         

Mostrar el registro completo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Buchin, Kevin; Buchin, Maike; Kreveld, Marc van; Löffler, Maarten; Luo, Jun; Silveira, Rodrigo Ignacio
Buchin, Kevin; Buchin, Maike; Kreveld, Marc van; Löffler, Maarten; Silveira, Rodrigo Ignacio; Wenk, Carola; Wiratma, Lionov
Agarwal, Pankaj; Aronov, Boris; Kreveld, Marc van; Löffler, Maarten; Silveira, Rodrigo Ignacio
Buchin, Maike; Driemel, Anne; Kreveld, Marc van; Sacristán Adinolfi, Vera
Buchin, Maike; Driemel, Anne; Kreveld, Marc van; Sacristán Adinolfi, Vera