{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T03:35:22Z","timestamp":1777520122552,"version":"3.51.4"},"reference-count":13,"publisher":"World Scientific Pub Co Pte Lt","issue":"01n02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2017,3]]},"abstract":"<jats:p> Let [Formula: see text] be a set of [Formula: see text] labeled points in the plane. The radial system of [Formula: see text] describes, for each [Formula: see text], the order in which a ray that rotates around [Formula: see text] encounters the points in [Formula: see text]. This notion is related to the order type of [Formula: see text], which describes the orientation (clockwise or counterclockwise) of every ordered triple in [Formula: see text]. Given only the order type, the radial system is uniquely determined and can easily be obtained. The converse, however, is not true. Indeed, let [Formula: see text] be the radial system of [Formula: see text], and let [Formula: see text] be the set of all order types with radial system [Formula: see text] (we define [Formula: see text] for the case that [Formula: see text] is not a valid radial system). Aichholzer et al. (Reconstructing Point Set Order Types from Radial Orderings, in Proc. ISAAC 2014) show that [Formula: see text] may contain up to [Formula: see text] order types. They also provide polynomial-time algorithms to compute [Formula: see text] when only [Formula: see text] is given. <\/jats:p><jats:p> We describe a new algorithm for finding [Formula: see text]. The algorithm constructs the convex hulls of all possible point sets with the radial system [Formula: see text]. After that, orientation queries on point triples can be answered in constant time. A representation of this set of convex hulls can be found in [Formula: see text] queries to the radial system, using [Formula: see text] additional processing time. This is optimal. Our results also generalize to abstract order types. <\/jats:p>","DOI":"10.1142\/s0218195917600044","type":"journal-article","created":{"date-parts":[[2017,9,14]],"date-time":"2017-09-14T06:24:13Z","timestamp":1505370253000},"page":"57-83","source":"Crossref","is-referenced-by-count":5,"title":["An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings"],"prefix":"10.1142","volume":"27","author":[{"given":"Oswin","family":"Aichholzer","sequence":"first","affiliation":[{"name":"Institute for Software Technology, Graz University of Technology, Graz, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vincent","family":"Kusters","sequence":"additional","affiliation":[{"name":"Department of Computer Science, ETH Z\u00fcrich, Z\u00fcrich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wolfgang","family":"Mulzer","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Freie Universit\u00e4t Berlin, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Pilz","sequence":"additional","affiliation":[{"name":"Department of Computer Science, ETH Z\u00fcrich, Z\u00fcrich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manuel","family":"Wettstein","sequence":"additional","affiliation":[{"name":"Department of Computer Science, ETH Z\u00fcrich, Z\u00fcrich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2017,9,13]]},"reference":[{"key":"S0218195917600044BIB003","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-014-9644-z"},{"key":"S0218195917600044BIB004","doi-asserted-by":"publisher","DOI":"10.1007\/BF01934990"},{"key":"S0218195917600044BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2012.01.005"},{"key":"S0218195917600044BIB007","doi-asserted-by":"publisher","DOI":"10.1137\/0215024"},{"key":"S0218195917600044BIB008","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00232-8"},{"key":"S0218195917600044BIB009","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511543340"},{"key":"S0218195917600044BIB011","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(80)90096-5"},{"key":"S0218195917600044BIB012","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(84)90050-5"},{"key":"S0218195917600044BIB013","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-55611-7"},{"key":"S0218195917600044BIB014","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-010-9320-x"},{"key":"S0218195917600044BIB017","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0082792"},{"key":"S0218195917600044BIB021","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/438\/08443"},{"key":"S0218195917600044BIB022","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195900000115"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195917600044","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T19:33:26Z","timestamp":1565120006000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195917600044"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3]]},"references-count":13,"journal-issue":{"issue":"01n02","published-online":{"date-parts":[[2017,9,13]]},"published-print":{"date-parts":[[2017,3]]}},"alternative-id":["10.1142\/S0218195917600044"],"URL":"https:\/\/doi.org\/10.1142\/s0218195917600044","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,3]]}}}