[{"_id":"1578","status":"public","type":"journal_article","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T06:51:43Z","citation":{"mla":"Cao, Thanhtung, et al. “Triangulations from Topologically Correct Digital Voronoi Diagrams.” Computational Geometry, vol. 48, no. 7, Elsevier, 2015, pp. 507–19, doi:10.1016/j.comgeo.2015.04.001.","apa":"Cao, T., Edelsbrunner, H., & Tan, T. (2015). Triangulations from topologically correct digital Voronoi diagrams. Computational Geometry. Elsevier. https://doi.org/10.1016/j.comgeo.2015.04.001","ama":"Cao T, Edelsbrunner H, Tan T. Triangulations from topologically correct digital Voronoi diagrams. Computational Geometry. 2015;48(7):507-519. doi:10.1016/j.comgeo.2015.04.001","short":"T. Cao, H. Edelsbrunner, T. Tan, Computational Geometry 48 (2015) 507–519.","ieee":"T. Cao, H. Edelsbrunner, and T. Tan, “Triangulations from topologically correct digital Voronoi diagrams,” Computational Geometry, vol. 48, no. 7. Elsevier, pp. 507–519, 2015.","chicago":"Cao, Thanhtung, Herbert Edelsbrunner, and Tiowseng Tan. “Triangulations from Topologically Correct Digital Voronoi Diagrams.” Computational Geometry. Elsevier, 2015. https://doi.org/10.1016/j.comgeo.2015.04.001.","ista":"Cao T, Edelsbrunner H, Tan T. 2015. Triangulations from topologically correct digital Voronoi diagrams. Computational Geometry. 48(7), 507–519."},"department":[{"_id":"HeEd"}],"title":"Triangulations from topologically correct digital Voronoi diagrams","publist_id":"5593","author":[{"first_name":"Thanhtung","last_name":"Cao","full_name":"Cao, Thanhtung"},{"orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert"},{"first_name":"Tiowseng","last_name":"Tan","full_name":"Tan, Tiowseng"}],"oa_version":"None","acknowledgement":"The research of the second author is partially supported by NSF under grant DBI-0820624 and by DARPA under grants HR011-05-1-0057 and HR0011-09-006\r\n","abstract":[{"text":"We prove that the dual of the digital Voronoi diagram constructed by flooding the plane from the data points gives a geometrically and topologically correct dual triangulation. This provides the proof of correctness for recently developed GPU algorithms that outperform traditional CPU algorithms for constructing two-dimensional Delaunay triangulations.","lang":"eng"}],"month":"08","intvolume":" 48","publisher":"Elsevier","quality_controlled":"1","scopus_import":1,"day":"01","language":[{"iso":"eng"}],"publication":"Computational Geometry","year":"2015","publication_status":"published","date_published":"2015-08-01T00:00:00Z","doi":"10.1016/j.comgeo.2015.04.001","issue":"7","volume":48,"date_created":"2018-12-11T11:52:49Z","page":"507 - 519"},{"author":[{"last_name":"Biedl","full_name":"Biedl, Therese","first_name":"Therese"},{"full_name":"Held, Martin","last_name":"Held","first_name":"Martin"},{"id":"4700A070-F248-11E8-B48F-1D18A9856A87","first_name":"Stefan","full_name":"Huber, Stefan","orcid":"0000-0002-8871-5814","last_name":"Huber"},{"first_name":"Dominik","full_name":"Kaaser, Dominik","last_name":"Kaaser"},{"last_name":"Palfrader","full_name":"Palfrader, Peter","first_name":"Peter"}],"publist_id":"5587","title":"Reprint of: Weighted straight skeletons in the plane","citation":{"short":"T. Biedl, M. Held, S. Huber, D. Kaaser, P. Palfrader, Computational Geometry: Theory and Applications 48 (2015) 429–442.","ieee":"T. Biedl, M. Held, S. Huber, D. Kaaser, and P. Palfrader, “Reprint of: Weighted straight skeletons in the plane,” Computational Geometry: Theory and Applications, vol. 48, no. 5. Elsevier, pp. 429–442, 2015.","ama":"Biedl T, Held M, Huber S, Kaaser D, Palfrader P. Reprint of: Weighted straight skeletons in the plane. Computational Geometry: Theory and Applications. 2015;48(5):429-442. doi:10.1016/j.comgeo.2015.01.004","apa":"Biedl, T., Held, M., Huber, S., Kaaser, D., & Palfrader, P. (2015). Reprint of: Weighted straight skeletons in the plane. Computational Geometry: Theory and Applications. Elsevier. https://doi.org/10.1016/j.comgeo.2015.01.004","mla":"Biedl, Therese, et al. “Reprint of: Weighted Straight Skeletons in the Plane.” Computational Geometry: Theory and Applications, vol. 48, no. 5, Elsevier, 2015, pp. 429–42, doi:10.1016/j.comgeo.2015.01.004.","ista":"Biedl T, Held M, Huber S, Kaaser D, Palfrader P. 2015. Reprint of: Weighted straight skeletons in the plane. Computational Geometry: Theory and Applications. 48(5), 429–442.","chicago":"Biedl, Therese, Martin Held, Stefan Huber, Dominik Kaaser, and Peter Palfrader. “Reprint of: Weighted Straight Skeletons in the Plane.” Computational Geometry: Theory and Applications. Elsevier, 2015. https://doi.org/10.1016/j.comgeo.2015.01.004."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"publisher":"Elsevier","quality_controlled":"1","page":"429 - 442","date_created":"2018-12-11T11:52:51Z","date_published":"2015-07-01T00:00:00Z","doi":"10.1016/j.comgeo.2015.01.004","year":"2015","has_accepted_license":"1","publication":"Computational Geometry: Theory and Applications","day":"01","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"type":"journal_article","pubrep_id":"475","status":"public","_id":"1584","file_date_updated":"2020-07-14T12:45:03Z","department":[{"_id":"HeEd"}],"date_updated":"2023-02-23T10:05:22Z","ddc":["000"],"scopus_import":1,"intvolume":" 48","month":"07","abstract":[{"lang":"eng","text":"We investigate weighted straight skeletons from a geometric, graph-theoretical, and combinatorial point of view. We start with a thorough definition and shed light on some ambiguity issues in the procedural definition. We investigate the geometry, combinatorics, and topology of faces and the roof model, and we discuss in which cases a weighted straight skeleton is connected. Finally, we show that the weighted straight skeleton of even a simple polygon may be non-planar and may contain cycles, and we discuss under which restrictions on the weights and/or the input polygon the weighted straight skeleton still behaves similar to its unweighted counterpart. In particular, we obtain a non-procedural description and a linear-time construction algorithm for the straight skeleton of strictly convex polygons with arbitrary weights."}],"oa_version":"Published Version","license":"https://creativecommons.org/licenses/by/4.0/","volume":48,"issue":"5","related_material":{"record":[{"id":"1582","status":"public","relation":"other"}]},"publication_status":"published","language":[{"iso":"eng"}],"file":[{"checksum":"5b33719a86f7f4c8e5dc62c1b6893f49","file_id":"5292","access_level":"open_access","relation":"main_file","content_type":"application/pdf","date_created":"2018-12-12T10:17:36Z","file_name":"IST-2016-475-v1+1_1-s2.0-S092577211500005X-main.pdf","creator":"system","date_updated":"2020-07-14T12:45:03Z","file_size":508379}]},{"quality_controlled":"1","publisher":"Elsevier","oa":1,"page":"120 - 133","date_published":"2015-02-01T00:00:00Z","doi":"10.1016/j.comgeo.2014.08.006","date_created":"2018-12-11T11:52:51Z","has_accepted_license":"1","year":"2015","day":"01","publication":"Computational Geometry: Theory and Applications","author":[{"last_name":"Biedl","full_name":"Biedl, Therese","first_name":"Therese"},{"first_name":"Martin","full_name":"Held, Martin","last_name":"Held"},{"id":"4700A070-F248-11E8-B48F-1D18A9856A87","first_name":"Stefan","last_name":"Huber","full_name":"Huber, Stefan","orcid":"0000-0002-8871-5814"},{"last_name":"Kaaser","full_name":"Kaaser, Dominik","first_name":"Dominik"},{"first_name":"Peter","full_name":"Palfrader, Peter","last_name":"Palfrader"}],"publist_id":"5589","title":"Weighted straight skeletons in the plane","citation":{"apa":"Biedl, T., Held, M., Huber, S., Kaaser, D., & Palfrader, P. (2015). Weighted straight skeletons in the plane. Computational Geometry: Theory and Applications. Elsevier. https://doi.org/10.1016/j.comgeo.2014.08.006","ama":"Biedl T, Held M, Huber S, Kaaser D, Palfrader P. Weighted straight skeletons in the plane. Computational Geometry: Theory and Applications. 2015;48(2):120-133. doi:10.1016/j.comgeo.2014.08.006","ieee":"T. Biedl, M. Held, S. Huber, D. Kaaser, and P. Palfrader, “Weighted straight skeletons in the plane,” Computational Geometry: Theory and Applications, vol. 48, no. 2. Elsevier, pp. 120–133, 2015.","short":"T. Biedl, M. Held, S. Huber, D. Kaaser, P. Palfrader, Computational Geometry: Theory and Applications 48 (2015) 120–133.","mla":"Biedl, Therese, et al. “Weighted Straight Skeletons in the Plane.” Computational Geometry: Theory and Applications, vol. 48, no. 2, Elsevier, 2015, pp. 120–33, doi:10.1016/j.comgeo.2014.08.006.","ista":"Biedl T, Held M, Huber S, Kaaser D, Palfrader P. 2015. Weighted straight skeletons in the plane. Computational Geometry: Theory and Applications. 48(2), 120–133.","chicago":"Biedl, Therese, Martin Held, Stefan Huber, Dominik Kaaser, and Peter Palfrader. “Weighted Straight Skeletons in the Plane.” Computational Geometry: Theory and Applications. Elsevier, 2015. https://doi.org/10.1016/j.comgeo.2014.08.006."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","scopus_import":1,"month":"02","intvolume":" 48","abstract":[{"text":"We investigate weighted straight skeletons from a geometric, graph-theoretical, and combinatorial point of view. We start with a thorough definition and shed light on some ambiguity issues in the procedural definition. We investigate the geometry, combinatorics, and topology of faces and the roof model, and we discuss in which cases a weighted straight skeleton is connected. Finally, we show that the weighted straight skeleton of even a simple polygon may be non-planar and may contain cycles, and we discuss under which restrictions on the weights and/or the input polygon the weighted straight skeleton still behaves similar to its unweighted counterpart. In particular, we obtain a non-procedural description and a linear-time construction algorithm for the straight skeleton of strictly convex polygons with arbitrary weights.","lang":"eng"}],"oa_version":"Published Version","volume":48,"issue":"2","related_material":{"record":[{"relation":"other","id":"1584","status":"public"}]},"publication_status":"published","file":[{"checksum":"c1ef67f6ec925e12f73a96b8fe285ab4","file_id":"5215","relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_name":"IST-2016-474-v1+1_1-s2.0-S0925772114000807-main.pdf","date_created":"2018-12-12T10:16:28Z","creator":"system","file_size":505987,"date_updated":"2020-07-14T12:45:02Z"}],"language":[{"iso":"eng"}],"type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"status":"public","pubrep_id":"474","_id":"1582","file_date_updated":"2020-07-14T12:45:02Z","department":[{"_id":"HeEd"}],"date_updated":"2023-02-23T10:05:27Z","ddc":["000"]},{"page":"243 - 247","date_published":"2015-02-01T00:00:00Z","doi":"10.1016/j.ipl.2014.09.021","date_created":"2018-12-11T11:52:51Z","has_accepted_license":"1","year":"2015","day":"01","publication":"Information Processing Letters","publisher":"Elsevier","quality_controlled":"1","oa":1,"publist_id":"5588","author":[{"last_name":"Biedl","full_name":"Biedl, Therese","first_name":"Therese"},{"last_name":"Held","full_name":"Held, Martin","first_name":"Martin"},{"last_name":"Huber","full_name":"Huber, Stefan","orcid":"0000-0002-8871-5814","first_name":"Stefan","id":"4700A070-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Dominik","full_name":"Kaaser, Dominik","last_name":"Kaaser"},{"first_name":"Peter","last_name":"Palfrader","full_name":"Palfrader, Peter"}],"title":"A simple algorithm for computing positively weighted straight skeletons of monotone polygons","citation":{"ista":"Biedl T, Held M, Huber S, Kaaser D, Palfrader P. 2015. A simple algorithm for computing positively weighted straight skeletons of monotone polygons. Information Processing Letters. 115(2), 243–247.","chicago":"Biedl, Therese, Martin Held, Stefan Huber, Dominik Kaaser, and Peter Palfrader. “A Simple Algorithm for Computing Positively Weighted Straight Skeletons of Monotone Polygons.” Information Processing Letters. Elsevier, 2015. https://doi.org/10.1016/j.ipl.2014.09.021.","ieee":"T. Biedl, M. Held, S. Huber, D. Kaaser, and P. Palfrader, “A simple algorithm for computing positively weighted straight skeletons of monotone polygons,” Information Processing Letters, vol. 115, no. 2. Elsevier, pp. 243–247, 2015.","short":"T. Biedl, M. Held, S. Huber, D. Kaaser, P. Palfrader, Information Processing Letters 115 (2015) 243–247.","apa":"Biedl, T., Held, M., Huber, S., Kaaser, D., & Palfrader, P. (2015). A simple algorithm for computing positively weighted straight skeletons of monotone polygons. Information Processing Letters. Elsevier. https://doi.org/10.1016/j.ipl.2014.09.021","ama":"Biedl T, Held M, Huber S, Kaaser D, Palfrader P. A simple algorithm for computing positively weighted straight skeletons of monotone polygons. Information Processing Letters. 2015;115(2):243-247. doi:10.1016/j.ipl.2014.09.021","mla":"Biedl, Therese, et al. “A Simple Algorithm for Computing Positively Weighted Straight Skeletons of Monotone Polygons.” Information Processing Letters, vol. 115, no. 2, Elsevier, 2015, pp. 243–47, doi:10.1016/j.ipl.2014.09.021."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","issue":"2","volume":115,"publication_status":"published","file":[{"content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_id":"5367","checksum":"2779a648610c9b5c86d0b51a62816d23","file_size":270137,"date_updated":"2020-07-14T12:45:03Z","creator":"system","file_name":"IST-2016-473-v1+1_1-s2.0-S0020019014001987-main.pdf","date_created":"2018-12-12T10:18:45Z"}],"language":[{"iso":"eng"}],"scopus_import":1,"month":"02","intvolume":" 115","abstract":[{"lang":"eng","text":"We study the characteristics of straight skeletons of monotone polygonal chains and use them to devise an algorithm for computing positively weighted straight skeletons of monotone polygons. Our algorithm runs in O(nlogn) time and O(n) space, where n denotes the number of vertices of the polygon."}],"oa_version":"Published Version","department":[{"_id":"HeEd"}],"file_date_updated":"2020-07-14T12:45:03Z","date_updated":"2021-01-12T06:51:45Z","ddc":["000"],"type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"status":"public","pubrep_id":"473","_id":"1583"},{"publication_identifier":{"eisbn":["978-3-319-27261-0"],"isbn":["978-3-319-27260-3"]},"publication_status":"published","language":[{"iso":"eng"}],"volume":9411,"abstract":[{"lang":"eng","text":"The straight skeleton of a polygon is the geometric graph obtained by tracing the vertices during a mitered offsetting process. It is known that the straight skeleton of a simple polygon is a tree, and one can naturally derive directions on the edges of the tree from the propagation of the shrinking process. In this paper, we ask the reverse question: Given a tree with directed edges, can it be the straight skeleton of a polygon? And if so, can we find a suitable simple polygon? We answer these questions for all directed trees where the order of edges around each node is fixed."}],"oa_version":"Preprint","alternative_title":["LNCS"],"scopus_import":"1","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1508.01076"}],"month":"11","intvolume":" 9411","date_updated":"2022-01-28T09:10:37Z","department":[{"_id":"HeEd"}],"_id":"1590","type":"book_chapter","conference":{"name":"GD: International Symposium on Graph Drawing","start_date":"2015-09-24","end_date":"2015-09-26","location":"Los Angeles, CA, United States"},"status":"public","year":"2015","day":"27","publication":"Graph Drawing and Network Visualization","page":"335 - 347","doi":"10.1007/978-3-319-27261-0_28","date_published":"2015-11-27T00:00:00Z","date_created":"2018-12-11T11:52:54Z","quality_controlled":"1","publisher":"Springer Nature","oa":1,"citation":{"mla":"Aichholzer, Oswin, et al. “Representing Directed Trees as Straight Skeletons.” Graph Drawing and Network Visualization, vol. 9411, Springer Nature, 2015, pp. 335–47, doi:10.1007/978-3-319-27261-0_28.","ieee":"O. Aichholzer et al., “Representing directed trees as straight skeletons,” in Graph Drawing and Network Visualization, vol. 9411, Springer Nature, 2015, pp. 335–347.","short":"O. Aichholzer, T. Biedl, T. Hackl, M. Held, S. Huber, P. Palfrader, B. Vogtenhuber, in:, Graph Drawing and Network Visualization, Springer Nature, 2015, pp. 335–347.","ama":"Aichholzer O, Biedl T, Hackl T, et al. Representing directed trees as straight skeletons. In: Graph Drawing and Network Visualization. Vol 9411. Springer Nature; 2015:335-347. doi:10.1007/978-3-319-27261-0_28","apa":"Aichholzer, O., Biedl, T., Hackl, T., Held, M., Huber, S., Palfrader, P., & Vogtenhuber, B. (2015). Representing directed trees as straight skeletons. In Graph Drawing and Network Visualization (Vol. 9411, pp. 335–347). Los Angeles, CA, United States: Springer Nature. https://doi.org/10.1007/978-3-319-27261-0_28","chicago":"Aichholzer, Oswin, Therese Biedl, Thomas Hackl, Martin Held, Stefan Huber, Peter Palfrader, and Birgit Vogtenhuber. “Representing Directed Trees as Straight Skeletons.” In Graph Drawing and Network Visualization, 9411:335–47. Springer Nature, 2015. https://doi.org/10.1007/978-3-319-27261-0_28.","ista":"Aichholzer O, Biedl T, Hackl T, Held M, Huber S, Palfrader P, Vogtenhuber B. 2015.Representing directed trees as straight skeletons. In: Graph Drawing and Network Visualization. LNCS, vol. 9411, 335–347."},"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","publist_id":"5581","author":[{"last_name":"Aichholzer","full_name":"Aichholzer, Oswin","first_name":"Oswin"},{"full_name":"Biedl, Therese","last_name":"Biedl","first_name":"Therese"},{"first_name":"Thomas","last_name":"Hackl","full_name":"Hackl, Thomas"},{"full_name":"Held, Martin","last_name":"Held","first_name":"Martin"},{"orcid":"0000-0002-8871-5814","full_name":"Huber, Stefan","last_name":"Huber","id":"4700A070-F248-11E8-B48F-1D18A9856A87","first_name":"Stefan"},{"last_name":"Palfrader","full_name":"Palfrader, Peter","first_name":"Peter"},{"last_name":"Vogtenhuber","full_name":"Vogtenhuber, Birgit","first_name":"Birgit"}],"article_processing_charge":"No","title":"Representing directed trees as straight skeletons"}]