{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T06:43:41Z","timestamp":1740120221528,"version":"3.37.3"},"reference-count":26,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01n02","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1526335"],"award-info":[{"award-number":["1526335"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1524455"],"award-info":[{"award-number":["1524455"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:p> Computational geometry algorithms branch on the signs of predicates. Prior predicate evaluation techniques are slow on degenerate (zero sign) predicates, especially on predicates on algebraic numbers. Degeneracy is common for predicates whose arguments have common antecedents. We present three randomized algorithms for degeneracy detection. The first algorithm uses modular arithmetic to detect degenerate predicates on rational numbers. The second algorithm uses quotient rings to reduce detecting degenerate predicates on algebraic numbers to multiple rational predicates, which can be evaluated deterministically or using the first algorithm. This algorithm is impractical because it is exponential in the number of algebraic numbers, yet it is still much faster than prior work that uses root separation bounds. The third algorithm uses a perturbation to eliminate degenerate algebraic predicates that are not identical to zero and a second perturbation to detect those that are. The first and third algorithms are incorporated into an exact geometric computation library. By sampling values generated by the algorithms, the library estimates the degeneracy detection failure probability over the lifetime of every calling program. We call this approach statistical degeneracy detection (SDD). Extensive testing shows that predicate evaluation is reliable and fast. <\/jats:p>","DOI":"10.1142\/s0218195922500054","type":"journal-article","created":{"date-parts":[[2022,10,6]],"date-time":"2022-10-06T11:30:02Z","timestamp":1665055802000},"page":"39-54","source":"Crossref","is-referenced-by-count":1,"title":["Efficient Predicate Evaluation Using Randomized Degeneracy Detection"],"prefix":"10.1142","volume":"32","author":[{"given":"Victor","family":"Milenkovic","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Miami, Coral Gables, Floridy 33124-4245, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elisha","family":"Sacks","sequence":"additional","affiliation":[{"name":"Computer Science Department, Purdue University, West Lafayette, Indiana 47907-2066, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2022,10,4]]},"reference":[{"key":"S0218195922500054BIB001","doi-asserted-by":"publisher","DOI":"10.1201\/9781420035315.ch41"},{"key":"S0218195922500054BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00231-6"},{"key":"S0218195922500054BIB003","first-page":"92","author":"Halperin D.","year":"2010","journal-title":"ICMS"},{"volume-title":"The LEDA Platform for Combinatorial and Geometric Computing","year":"1999","author":"Melhorn K.","key":"S0218195922500054BIB005"},{"key":"S0218195922500054BIB006","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9132-4"},{"key":"S0218195922500054BIB007","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970906"},{"key":"S0218195922500054BIB008","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009321"},{"key":"S0218195922500054BIB009","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00101-7"},{"key":"S0218195922500054BIB011","doi-asserted-by":"publisher","DOI":"10.1016\/j.jlap.2004.07.006"},{"key":"S0218195922500054BIB012","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2019.07.001"},{"key":"S0218195922500054BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.04.014"},{"key":"S0218195922500054BIB014","first-page":"91","volume-title":"Proceedings of the Canadian Conference on Computational Geometry","author":"Masterjohn J.","year":"2018"},{"key":"S0218195922500054BIB015","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-68530-8_13"},{"key":"S0218195922500054BIB016","doi-asserted-by":"publisher","DOI":"10.1109\/TASE.2013.2277781"},{"key":"S0218195922500054BIB017","doi-asserted-by":"publisher","DOI":"10.1145\/1236463.1236468"},{"key":"S0218195922500054BIB018","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2013.08.035"},{"key":"S0218195922500054BIB019","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2018.10.003"},{"key":"S0218195922500054BIB020","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195919500067"},{"key":"S0218195922500054BIB021","doi-asserted-by":"publisher","DOI":"10.1142\/S021819590700229X"},{"key":"S0218195922500054BIB022","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195910003402"},{"key":"S0218195922500054BIB023","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2010.09.004"},{"key":"S0218195922500054BIB024","first-page":"242","author":"Avnaim F.","year":"1987","journal-title":"Symposium on Computational Geometry"},{"key":"S0218195922500054BIB025","doi-asserted-by":"publisher","DOI":"10.1002\/nme.3016"},{"key":"S0218195922500054BIB026","doi-asserted-by":"publisher","DOI":"10.1007\/s00366-013-0331-0"},{"key":"S0218195922500054BIB027","first-page":"223","volume-title":"Proceedings of the Canadian Conference on Computational Geometry","author":"Arluck C.","year":"2018"},{"key":"S0218195922500054BIB028","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2017.05.017"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195922500054","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,18]],"date-time":"2022-10-18T10:14:35Z","timestamp":1666088075000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0218195922500054"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3]]},"references-count":26,"journal-issue":{"issue":"01n02","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["10.1142\/S0218195922500054"],"URL":"https:\/\/doi.org\/10.1142\/s0218195922500054","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"type":"print","value":"0218-1959"},{"type":"electronic","value":"1793-6357"}],"subject":[],"published":{"date-parts":[[2022,3]]}}}