{"id":20247,"date":"2018-03-09T09:09:31","date_gmt":"2018-03-09T09:09:31","guid":{"rendered":"https:\/\/www.deberes.net\/tesis\/sin-categoria\/problemas-de-etiquetado-complejidad-computacional\/"},"modified":"2018-03-09T09:09:31","modified_gmt":"2018-03-09T09:09:31","slug":"problemas-de-etiquetado-complejidad-computacional","status":"publish","type":"post","link":"https:\/\/www.deberes.net\/tesis\/sevilla\/problemas-de-etiquetado-complejidad-computacional\/","title":{"rendered":"Problemas de etiquetado: complejidad computacional"},"content":{"rendered":"<h2>Tesis doctoral de <strong> Pedro Reyes Colum\u00e9 <\/strong><\/h2>\n<p>El etiquetado es una de las grandes \u00e1reas de investigaci\u00f3n dentro de la geometr\u00eda computacional. As\u00ed lo avalan la gran cantidad de trabajos que, motivados por sus aplicaciones en diferentes \u00e1reas como la cartograf\u00eda, se elaboran por parte de la comunidad cient\u00edfica internacional y el gran n\u00famero de conferencias y encuentros que sobre la materia se realizan peri\u00f3dicamente. este inter\u00e9s queda refrendado por el hecho de que la acm lo incoropora como \u00e1rea preferente de investigaci\u00f3n dentro del campo de la geometr\u00eda computacional.  dentro de este campo, y debido a la enorme complejidad de sus problemas, aparecen multitud de variantes del problema general. Una de estas variantes es la consistente en el etiquetado de puntos con etiquetas rectangulares. esta variante presenta dos modelos: etiquetado con etiquetas fijas, donde cada etiqueta puede ser colocada en un n\u00famero finito de puntos, y etiquetado con etiquetas deslizantes, de forma que cada etiqueta puede ser colocada de forma que el punto quede situado a cualquiera de los puntos del contorno de la etiqueta.  en numerosos problemas de etiquetado (redes de metro, mapas de carretera) los puntos a etiquetar son alineados. Estos modelos de etiquetado son el objeto de estudio de la primera parte de la memoria, donde se estudiar\u00e1 la complejidad computacional de los distintos problemas que se pueden plantear, tanto cuando los puntos est\u00e9n situados sobre una l\u00ednea horizontal como en una l\u00ednea oblicua. Estudiaremos en esta primera parte tanto los problemas de decisi\u00f3n como los correspondientes problemas de optimizaci\u00f3n del tama\u00f1o de las etiquetas.  motivado por la naturaleza np-dura de uno de estos problemas (el correspondiente a etiquetados de puntos alineados sobre una l\u00ednea horizontal con etiquetas rectangulares deslizantes) y de otro problema de etiquetado (etiquetado con etiquetas rectangulares de \u00e1rea m\u00ednima y v\u00e9rtices prefijados) y la relaci\u00f3n de estos problemas qu<\/p>\n<p>&nbsp;<\/p>\n<h3>Datos acad\u00e9micos de la tesis doctoral \u00ab<strong>Problemas de etiquetado: complejidad computacional<\/strong>\u00ab<\/h3>\n<ul>\n<li><strong>T\u00edtulo de la tesis:<\/strong>\u00a0 Problemas de etiquetado: complejidad computacional <\/li>\n<li><strong>Autor:<\/strong>\u00a0 Pedro Reyes Colum\u00e9 <\/li>\n<li><strong>Universidad:<\/strong>\u00a0 Sevilla<\/li>\n<li><strong>Fecha de lectura de la tesis:<\/strong>\u00a0 29\/11\/2002<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<h3>Direcci\u00f3n y tribunal<\/h3>\n<ul>\n<li><strong>Director de la tesis<\/strong>\n<ul>\n<li>Alberto M\u00e1rquez P\u00e9rez<\/li>\n<\/ul>\n<\/li>\n<li><strong>Tribunal<\/strong>\n<ul>\n<li>Presidente del tribunal: inmaculada Perez de guzman molina <\/li>\n<li> Ch\u00e1vez de diego Mar\u00eda Jos\u00e9 (vocal)<\/li>\n<li>clara isabel Grima ruiz (vocal)<\/li>\n<li>claudia Iturriaga-vel\u00e1zquez (vocal)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Tesis doctoral de Pedro Reyes Colum\u00e9 El etiquetado es una de las grandes \u00e1reas de investigaci\u00f3n dentro de la geometr\u00eda [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"footnotes":""},"categories":[10715],"tags":[10831,61682,58350,61683,24725,61681],"class_list":["post-20247","post","type-post","status-publish","format-standard","hentry","category-sevilla","tag-alberto-marquez-perez","tag-chavez-de-diego-maria-jose","tag-clara-isabel-grima-ruiz","tag-claudia-iturriaga-velazquez","tag-inmaculada-perez-de-guzman-molina","tag-pedro-reyes-colume"],"_links":{"self":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/20247","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/comments?post=20247"}],"version-history":[{"count":0,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/20247\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/media?parent=20247"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/categories?post=20247"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/tags?post=20247"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}