{"id":352814,"date":"2017-01-14T20:57:32","date_gmt":"2017-01-15T04:57:32","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/?post_type=msr-research-item&#038;p=352814"},"modified":"2018-10-16T20:20:10","modified_gmt":"2018-10-17T03:20:10","slug":"minimum-steiner-trees-normed-planes","status":"publish","type":"msr-research-item","link":"https:\/\/www.microsoft.com\/en-us\/research\/publication\/minimum-steiner-trees-normed-planes\/","title":{"rendered":"Minimum Steiner Trees in Normed Planes"},"content":{"rendered":"<section id=\"Abs1\" class=\"Abstract\" lang=\"en\" tabindex=\"-1\">\n<p class=\"Para\">A minimum Steiner tree for a given set<em class=\"EmphasisTypeItalic \">X<\/em> of points is a network interconnecting the points of<em class=\"EmphasisTypeItalic \">X<\/em> having minimum possible total length. In this note we investigate various properties of minimum Steiner trees in normed planes, i.e., where the \u201cunit disk\u201d is an arbitrary compact convex centrally symmetric domain<em class=\"EmphasisTypeItalic \">D<\/em> having nonempty interior. We show that if the boundary of<em class=\"EmphasisTypeItalic \">D<\/em> is strictly convex and differentiable, then each edge of a full minimum Steiner tree is in one of three fixed directions. We also investigate the Steiner ratio<em class=\"EmphasisTypeItalic \">\u03c1<\/em>(<em class=\"EmphasisTypeItalic \">D<\/em>) for<em class=\"EmphasisTypeItalic \">D<\/em>, and show that, for any<em class=\"EmphasisTypeItalic \">D<\/em>, 0.623<<em class=\"EmphasisTypeItalic \">\u03c1<\/em>(<em class=\"EmphasisTypeItalic \">D<\/em>)<0.8686.<\/p>\n<\/section>\n<div class=\"HeaderArticleNotes\">\n<aside class=\"ArticleNote ArticleNoteMisc\">\n<p class=\"SimplePara\">Part of this work was done while Ding-Zhu Du was at the Computer Science Department, Princeton University and the Center for Discrete Mathematics and Theoretical Computer Science at Rutgers. Supported by NSF under Grant STC88-09648.<\/p>\n<\/aside>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>A minimum Steiner tree for a given setX of points is a network interconnecting the points ofX having minimum possible total length. In this note we investigate various properties of minimum Steiner trees in normed planes, i.e., where the \u201cunit disk\u201d is an arbitrary compact convex centrally symmetric domainD having nonempty interior. We show that [&hellip;]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr-author-ordering":null,"msr_publishername":"Springer Link","msr_publisher_other":"","msr_booktitle":"","msr_chapter":"4","msr_edition":"Discrete & Computational Geometry","msr_editors":"","msr_how_published":"","msr_isbn":"","msr_issue":"","msr_journal":"","msr_number":"","msr_organization":"","msr_pages_string":"351\u2013370","msr_page_range_start":"351","msr_page_range_end":"370","msr_series":"","msr_volume":"9","msr_copyright":"","msr_conference_name":"Discrete & Computational Geometry","msr_doi":"10.1007\/BF02189328","msr_arxiv_id":"","msr_s2_paper_id":"","msr_mag_id":"","msr_pubmed_id":"","msr_other_authors":"","msr_other_contributors":"","msr_speaker":"","msr_award":"","msr_affiliation":"","msr_institution":"","msr_host":"","msr_version":"","msr_duration":"","msr_original_fields_of_study":"","msr_release_tracker_id":"","msr_s2_match_type":"","msr_citation_count_updated":"","msr_published_date":"1993-04-01","msr_highlight_text":"","msr_notes":"","msr_longbiography":"","msr_publicationurl":"http:\/\/link.springer.com\/article\/10.1007\/BF02189328","msr_external_url":"","msr_secondary_video_url":"","msr_conference_url":"","msr_journal_url":"","msr_s2_pdf_url":"","msr_year":0,"msr_citation_count":0,"msr_influential_citations":0,"msr_reference_count":0,"msr_s2_match_confidence":0,"msr_microsoftintellectualproperty":true,"msr_s2_open_access":false,"msr_s2_author_ids":[],"msr_pub_ids":[],"msr_hide_image_in_river":0,"footnotes":""},"msr-research-highlight":[],"research-area":[13562],"msr-publication-type":[193716],"msr-publisher":[],"msr-focus-area":[],"msr-locale":[268875],"msr-post-option":[],"msr-field-of-study":[],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-352814","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-computer-vision","msr-locale-en_us"],"msr_publishername":"Springer Link","msr_edition":"Discrete & Computational Geometry","msr_affiliation":"","msr_published_date":"1993-04-01","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"351\u2013370","msr_chapter":"4","msr_isbn":"","msr_journal":"","msr_volume":"9","msr_number":"","msr_editors":"","msr_series":"","msr_issue":"","msr_organization":"","msr_how_published":"","msr_notes":"","msr_highlight_text":"","msr_release_tracker_id":"","msr_original_fields_of_study":"","msr_download_urls":"","msr_external_url":"","msr_secondary_video_url":"","msr_longbiography":"","msr_microsoftintellectualproperty":1,"msr_main_download":"","msr_publicationurl":"http:\/\/link.springer.com\/article\/10.1007\/BF02189328","msr_doi":"10.1007\/BF02189328","msr_publication_uploader":[{"type":"url","title":"http:\/\/link.springer.com\/article\/10.1007\/BF02189328","viewUrl":false,"id":false,"label_id":0},{"type":"doi","title":"10.1007\/BF02189328","viewUrl":false,"id":false,"label_id":0}],"msr_related_uploader":"","msr_citation_count":0,"msr_citation_count_updated":"","msr_s2_paper_id":"","msr_influential_citations":0,"msr_reference_count":0,"msr_arxiv_id":"","msr_s2_author_ids":[],"msr_s2_open_access":false,"msr_s2_pdf_url":null,"msr_attachments":[{"id":0,"url":"http:\/\/link.springer.com\/article\/10.1007\/BF02189328"}],"msr-author-ordering":[{"type":"text","value":"Ding-Zhu Du","user_id":0,"rest_url":false},{"type":"text","value":"Biao Gao","user_id":0,"rest_url":false},{"type":"text","value":"Ronald L. Graham","user_id":0,"rest_url":false},{"type":"user_nicename","value":"zliu","user_id":35148,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=zliu"},{"type":"text","value":"Peng-Jun Wan","user_id":0,"rest_url":false}],"msr_impact_theme":[],"msr_research_lab":[],"msr_event":[],"msr_group":[],"msr_project":[],"publication":[],"video":[],"msr-tool":[],"msr_publication_type":"inproceedings","related_content":[],"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/352814","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":1,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/352814\/revisions"}],"predecessor-version":[{"id":526810,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/352814\/revisions\/526810"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=352814"}],"wp:term":[{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=352814"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=352814"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=352814"},{"taxonomy":"msr-publisher","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publisher?post=352814"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=352814"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=352814"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=352814"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=352814"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=352814"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=352814"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=352814"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=352814"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}