{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,4,19]],"date-time":"2023-04-19T11:27:34Z","timestamp":1681903654587},"reference-count":12,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2005,12]]},"abstract":"<jats:p> A simple polyhedron is weakly-monotonic in direction [Formula: see text] provided that the intersection of the polyhedron and any plane with normal [Formula: see text] is simply-connected (i.e. empty, a point, a line-segment or a simple polygon). Furthermore, if the intersection is a convex set, then the polyhedron is said to be weakly-monotonic in the convex sense. Toussaint<jats:sup>10<\/jats:sup> introduced these types of polyhedra as generalizations of the 2-dimensional notion of monotonicity. We study the following recognition problems: <\/jats:p><jats:p> Given a simple n-vertex polyhedron in 3-dimensions, we present an O(n log n) time algorithm to determine if there exists a direction [Formula: see text] such that when sweeping over the polyhedron with a plane in direction [Formula: see text], the cross-section (or intersection) is a convex set. If we allow multiple convex polygons in the cross-section as opposed to a single convex polygon, then we provide a linear-time recognition algorithm. For simply-connected cross-sections (i.e. the cross-section is empty, a point, a line-segment or a simple polygon), we derive an O(n<jats:sup>2<\/jats:sup>) time recognition algorithm to determine if a direction [Formula: see text] exists. <\/jats:p><jats:p> We then study variations of monotonicity in 2-dimensions, i.e. for simple polygons. Given a simple n-vertex polygon P, we can determine whether or not a line \u2113 can be swept over P in a continuous manner but with varying direction, such that any position of \u2113 intersects P in at most two edges. We study two variants of the problem: one where the line is allowed to sweep over a portion of the polygon multiple times and one where it can sweep any portion of the polygon only once. Although the latter problem is slightly more complicated than the former since the line movements are restricted, our solutions to both problems run in O(n<jats:sup>2<\/jats:sup>) time. <\/jats:p>","DOI":"10.1142\/s0218195905001877","type":"journal-article","created":{"date-parts":[[2006,1,3]],"date-time":"2006-01-03T06:55:56Z","timestamp":1136271356000},"page":"591-608","source":"Crossref","is-referenced-by-count":7,"title":["GENERALIZING MONOTONICITY: ON RECOGNIZING SPECIAL CLASSES OF POLYGONS AND POLYHEDRA"],"prefix":"10.1142","volume":"15","author":[{"given":"PROSENJIT","family":"BOSE","sequence":"first","affiliation":[{"name":"School of Computer Science, Carleton University, 1125 Colonel By Drive, Ottawa, Canada, K1S 5B6, Canada"}]},{"given":"MARC","family":"VAN KREVELD","sequence":"additional","affiliation":[{"name":"Institute of Information and Computing Science, Utrecht University, P.O. Box 80.089, 3508 TB, Utrecht, The Netherlands"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/S0010-4485(97)00075-4"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03427-9"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00022-2"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1493"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195992000160"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(92)90010-P"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1515\/9781400881802"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90091-0"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(94)90020-5"},{"key":"rf10","doi-asserted-by":"crossref","unstructured":"G. T.\u00a0Toussaint, Computational Geometry, ed. G. T.\u00a0Toussaint (North-Holland, Amsterdam, Netherlands, 1985)\u00a0pp. 335\u2013375.","DOI":"10.1016\/B978-0-444-87806-9.50018-9"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1201\/9781420035315"},{"key":"rf12","volume-title":"Handbook of Computational Geometry","author":"Sack J.-R.","year":"2000"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195905001877","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:29:01Z","timestamp":1565123341000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195905001877"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,12]]},"references-count":12,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2005,12]]}},"alternative-id":["10.1142\/S0218195905001877"],"URL":"https:\/\/doi.org\/10.1142\/s0218195905001877","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,12]]}}}