Skip to Content.
Sympa Menu

cgal-discuss - [cgal-discuss] Trapezoidal decomposition in linear time

Subject: CGAL users discussion list

List archive

[cgal-discuss] Trapezoidal decomposition in linear time


Chronological Thread 
  • From: Matthew Hall <>
  • To:
  • Subject: [cgal-discuss] Trapezoidal decomposition in linear time
  • Date: Mon, 27 Nov 2023 09:03:04 -0500
  • Authentication-results: mail3-smtp-sop.national.inria.fr; spf=None ; spf=Pass ; spf=None
  • Ironport-data: A9a23:wCKRd6/oc+sZKP0FRxbvDrUDc3qTJUtcMsCJ2f8bNWPcYEJGY0x3m zMdXj/XOvzbYmrzeIx1a4zipk9UscTXxoBjHARsqC1EQiMRo6IpJ/zJdxaqZ3v6wu7rFR88s Z1GMrEsCOhuExcwcz/0auCJQUFUjP3OHPymYAL9EngZbRd+Tys8gg5Ulec8g4p56fC0GArlV ena+qUzA3f7nWYoWo4ow/jb8kg25a6t4GlwUmEWPJingneOzxH5M7pEfcldH1OgKqFIE+izQ fr0zb3R1gs1KD9wYj8Nuu+TnnwiGtY+DyDW4pZlc/TKbix5m8AH+v1T2Mzwxqtgo27hc9hZk L2hvHErIOsjFvWkdO81C3G0H8ziVEHvFXCuzXWX6KSuI0P6n3TE6q5TDUU6ZKQk9vdPJk5E6 dkBaxo2YUXW7w626OrTpuhEg80iKIzmMNpatCw6iz7eCvkiTNbIRKCiCd1whm9hwJATW6yGN 4xEM1KDbzyYC/FLElIeFI4+kfjunD//ejlcgE6Sv60x/2/W0Up62dABNfKKIIPSG5wIwi50o ErWwVqnHiE+BOWhyCqP0mqnqv6UwgDkDdd6+LqQraMz2ALCmAT/EiY+XlSypby1i1W1RslEA 1cF/zIn66k07k2iCNfnNyBUu1aBtx8YHtdcSqg0tVvLxa3T7AKUQGMDS1atdeDKqucfHgEr0 lPQtu/lFARIn7eJbGve3Iyb+Gba1TcuEUcOYioNTA0g6tbloZ0ugh+ncjqFOP7r5jESMWGvq w1mvBQDa6MvYdnnPphXEHjCijOo45XFF0s7u1+RUWWi4Qd0IoWiYuRECGQ3D94Rc+51rXHY4 xDofvRyCshQV/lhcwTTHY0w8EmBvartDdElqQcH82Md3zqs4WW/Wotb/StzIkxkWu5dJmewO BWI5V0Lu8ELVJdPUUORS9LvYyjN5fiwfekJqtiNMbKin7AoKFHeoXwzPyZ8IUizyhJzzsnTx qt3ge73UC9CVvU5pNZHb+ga1rAvy2g/w2iVLa0XPDz2uYdykEW9EO9fWHPXNr5RxPrd/G39r YwDX+PUkE43eLOlMkHqHXs7dw9iwY4TXsCo9aS6t4erfmJbJY3WI6KImup5I9I1wsy4VI7gp xmAZ6OR83Kn7VWvFOlAQikLhGrHDMkj/0EodzchJ0ip0HUFaIOipvVXPZgucLVtsKQpwfdoR rNXM4+NE9ZeeAThoj49VJjaqJA9VRKJgQnVATGpTgJidLFdRivI2OTeQC3RyAc0ABGaj/AO+ 4+b6luDQL4oZRhTM8LNWff+k3KzpSc8ncxxbWvpI/5SWh3mq6p0ISrLkPUHHtw9czjC4hC41 A+mJwgSiseQgo0y8fjP3bulqaXwGcRAP0NqJUvpxpfoCnCC5Uul44tLcNjQTADnTGmupZmTP 7RE/c/zINgsvQhssbMlN51J0Khnxd/kh4EC/zReBH+RMmiaUOJxEEKng/tKmLZGnIJCmA2MX UmKxNlWFJOJNO7hE38TPAAVVfuC595Fhgjt6ekJH2ui6B9V5LanVWBgDyuIggFZL5p3N9oB6 sUls8g09Qe+q0QLNvCrsyNqzFmPf0cwC/gfipInAYHQmlUKzHNGasfiESPY2syEROhNFUgIG QWqopT+qY5S/HefTEprJ0PxhbJcob8spCF1yEQzIgXVu9jd2d4y8h5j0RU2aQV3lh8c8fx5P FJ1PX1IOJTU0jZMr+pAVlCKBAtuKkC4+Evw6l1Rj0zfbRCieVLsJV0HG9Sm3R4mqjpHXz55+ Lq49j7UYQzydpus4hpoCF9XlfPzaPdQqCvAoZmDNOaYFcAYZTHFvPefVVAQoUG6PfJr1Vz1n sg0zuNecqahCDUxpZc8AIyk1bg9bhCICWhBYPN59pMyAmDuV2Cu6AeKNnyOVJtBF97S/W+8L v5eFMZFehC99SSJ9xQwJ6oHJZ1ql/8IuvsGXJ7WJlA9jrjOlQox7ars9RX/ilQ7HPRos8I2c b3Kexy4T2e/uHpzmk32lvdiBFaWW9c/STPZ4PGU68QMTpIKj/Ftexo905yypHSkDzFk9BO14 iLGPq/f8PN++7tVj6/TI/xmBliyI4miUu6nzR2C6YVSTNLQMPXhsxEehUnnMj93Y5oQeYVTv pacvOHn2HjquO4NbFnYvJ2aBYxl1N6XXtcLAvnoLXJfozSOaPXs7zQH5Wq8D55Dy/FZ2eWKW Cq6b5GWWeMOetIA2kBQVTdSIywdB4vzcK3kgyG39NaIKxoF1D34PMGVzmDoYU5bZx03FcXHU CGsgMmX5/dcsIhoLz0HDas/A5ZHfXnSaZF/fNj17TSlHm2kh22ZgYTblD0i1CrqD0eVG8Or8 LPHQRnDLC6Jgp/q9+0AkYJOvUwwNk1f0NkAJhdXv5Y8jj2hF2cJINgMKZhMWNkejiX204q+f z3XKncrDSLmRzlfbBHg+5LZUxyCAvAVcMLMTtDzE5h4tw/tbG9BPFdgysuky3J/ez+mwe3+b N9DoDv/OR++xpwvTuEWjhB+bSGL2duCrk/kO2ik+yAxP/raKakNzntnAA1ISGrMGqkhUW3Vc HMtSzksrF6TECbM/AUJR5KRMA0epjTp0zItcGGEyb4zfmldIPJokJXCBg047lHPgAnm6lLDq bMbilZhO1yr50E=
  • Ironport-hdrordr: A9a23:qavIL6OwRmcZwcBcTkqjsMiBIKoaSvp037By7TEWdfU0SKelf8 DHppQmPGzP+U8ssRAb6K290cy7LE80mqQFhbX5UY3NYOCEghrVEGgB1/qE/9SIIUSXnIIz6U 4KSdkcNDSENykesS+M2njbLz9P+ri6GYmT9JjjJjxWPHlXgulbnnxEIzfeKVduTA1KQbIyCZ qb4aN81kmdUEVSVd6jDn0JG9Deq8HG0LLqCCR2diIP2U20lyqh7LO/KRSCwRsEOgk/v4sKwC z+igT86+GZv+umzwK07R6i0315oqqa9ud+
  • Ironport-phdr: A9a23:nxbygxeDd4W1cmK5Q6ZSgwt+lGM+ANTLVj580XLHo4xHfqnrxZn+J kuXvawr0AWZG9yFsrkZ1KL/iOPJZy8p2dW7jDg6aptCVhsI2409vjcLJ4q7M3D9N+PgdCcgH c5PBxdP9nC/NlVJSo6lPwWB6nK94iQPFRrhKAF7Ovr6GpLIj8Swyuu+54Dfbx9HiTajYr5+N gi6oATMusUZgYZvKLs6xwfUrHdPZ+lZymRkKE6JkRr7+sm+4oNo/T5Ku/Im+c5AUKH6cLo9Q LdFEjkoMH076dPyuxXbQgSB+nUTUmMNkhpVGAfF9w31Xo3wsiThqOVw3jSRMNDsQrA1XTSi6 LprSAPthSwaOTM17H3bh8pth69dvRmvpQFww5TMbY6aNPRwcKDTc84ES2VdRcteTTBND5mmY ocTE+YMP+BVpJT9qVsUqhu+ABGhCuT1xT9Umn/23bM10uo8Gg/ExgMgG9YOu2nTodXwLqgST fy1zKnWwjTNdf9Wwy3x6IjSfRAlpfGBRq5wcc3LyUkoEQPFklKQqYn4Pz+PyusCqXGW4ux9X u2gl2ApsRt+oiSzxsgykInJgJoYxk3a+St2wYs5OMO1RkB0bNO5DZddtTyXOpdyT84iQWxlu Cg3xqEJtJOnYiUHyIkryh7bZvGHfIWF4RHuWfqMLDp+mXlre6q/ig6s/US8zuDwTMq53VZQo iZbjtXBtWoB2hzN5sWBV/Bw4EOh2SuU1wDP9O5EO106lavaKpE/2rM8ipweulnZECDsgkX5l qqWe10k+ue27+TnZa3rppqGOI91jgHyK7ohldGiDeghPAgDX3aX9f6z1L3k+k35T7FKgeMsn qbFt5DaINwXpq+/AwBLzoYu8wizAyui3dgCnnQKLEhJdAybg4XqIV3DIO70Ae+6g1u2kTdrw /7GPqfmApXINnXDla3ufaph605c1gUyw8pT54hOBrEBOv3zXkvxucfEDh8+KQy0xODnCMl61 oMbRGKDGLOWP7nKvV+O/e0gO/OMa5MNuDbhN/gl4ObjgWIhlV8HYaapxYcXaGy/Hvl+P0qZb mDjgtMYHWgXvwo+V/DliECZUT5IfHuyRKI95jQjCI28F4vDR4atgKaA3CihBJFWaHpGWRiwF iLjeIyAHvsNcymPOdRJkzoeVLHnRZVy+wupsVrfwqZ7LufLsg0RsZargN18+/HTmA5073p0B sCZ+32KVWZygmQNWnk91fYs8gRG1l6f3P0g0LRjHttJ6qYROu9bHZvVzughTsv3RhqEZdCRD lCvXtShBzg1CNM32d4HJUhnSJ25lh6W+S2sDvcOkqCTQoQu+/fZ1mTtJ8tijWyA1KAli3E6R dFIM3Ghg7M5/AGAT5XRnRChnr2xPb8ZwDaL8W6CyWSUu0QNVQdsTaXIQjYFIEvfqdDR+kTYS LmyDrE6dABImoaZMqUfTNrvgB1dQev7ftTTZ2Xkg2CrGROB3a+BdqLvcmQZmSjRUQ0KzlpV8 nGBOgwzQCympgoyFRRIElTiKwPp+Oh68zagS1MsihqNdwtn3qa0/RgcgbqdTekS1/QKonVpr TI8B1u709/MbrjI7wN8YKVRZ88861ZbxCrYsQJ6JJmpM6FlgBYXbQ12u0rk0xg/BJ9HlIAmq 3YjzQw6Lqz9shsJcjqEwZD9JfvNbGn7+BSHd6nM3VfC19OLvKwGqbw5p1jloAC1Bx866Xw0t rsdm3CY55jMEE8TScerChdxp0U8/emKJHRntOa2nTV2PKK5syHPwYcsDeohkVO7estHdbiDD En0GtEbAM6nLKornUKoZ1QKJrM3luZ8MsW4ev+BwKPuMvxnmWfsiG1b/IBwzQSWsSp1Turgw 5EfxPeE2Q6aETz1xgTE0Ii/icVfaDceE3Dqgy3tGJJRa7I0Z8ALAGOqC9Gw3NJ4m5noRjhT/ RTwYjFOkN/sch2UYVvn2ARW3klCun2rlxyzyDlsmi0opK6StMDX69zrbwFPemtCRW05yEzpP ZDxlNcCGk6hcwkukhKho0f83alS4qplfSHfRkJBfi6+KG8HMOP4s7Oef85C99Uy9yVeVOCUf VeATbjhpB4HlSjqV2dT3zE0cTi2t46xxUQrzjLAaiwr/DyEI4l53nK9rJTESORU3yYaSSUwk jTRClWmfpGo8diSi5bfo7W7XmOlWIdUdHqjxoeBuS2noGxyVEfnzrbjx5u9SVh8jHWosrsiH T/Fpxv9fITxgqGzMOY8O1JtGEe58M1iXId3joo3gpgUn3kcnJScu3QdwgKReZ1W37zzaH0VS HsF2dnQtULg0VF/Ln+WgZi/VnyZxuN9YMO9ZH8R3z975MkAW8L2pPRU2DB4pFa1t1ebZPFhg jcQ1r00rn4Th+UhpA03ySOBBbUPW0JRd3+J9VzA/5W1q6NZY3yqeL672R9lnNyvO7qFpxlVR HfzfppxVT819Mh0N0jAlWHi8oyxMseFdsod71fH9nWIx/gQMp86keAGwDZqKX6o92Nw0PY11 FRvxc3o59XBcjQ1uvjlXVgAcWepL8ILpmOz0eAExZ3Qht73WM0mQ2RuPtOgTOr0QmxM862/b UDWVmV78C/TGKKDT1HBrh06/jSfS9bzcCvPbHgBkYc9Hl/EeAoG0VpSBHJjzvtbXkir3JCzL xs/v2pMoAa+8lwVlKppL0WtCz+P4l73NXFkDsDYdkMe7xketR6KaorHv741R2cAucT/yW7FY m2DO1YSVTBPChHCXgqzeOHpvIaI8vDEVLDncb2TMfPX+LYYD7DRlNquytc0pW/ScJ/Ubz85V btjnRMSOBIxU9LQnzFFI8AOvwTKacPT5BK1+yks69u67OyuQwX3o42GF7pVN9xrvRGwm6aKc eCK1m5/Ln5D25UAyGWtqvBX1UMOiyxoazimEKgR/S/LQqXKn6ZLDhkdIyptPcpM5qg400FDI 8newt/y07d5iLYyBTInHRT5ndq1YMURP2ynHFbOBULOObjfYDOWmYf4ZqSzTbAWh+JR9lWxt TudD07/L2GDmj3uBHXNealHiCCWOgAbuZnoKE48Tzi+Coi+OlvmaowS73V+27A/i3LUOHRJN DF9dxgItbiM9WZDhe05HWVd731jJO3CmiCD7uCeJIxF1JkjSilyie9e52w3jrVP6yQRDvl8h DfSo8EouRemm+2L4iZgSh1ItjFOmcSAtA8xXMeRvokFQnvC8B8XuC+IDA8WotJ+FtD1k6VZy 9yKma6qbTkfqZTb+swTA8WSI8WCeilEU1KhCHvfCw0LSiSuPGfUihlGkf2cwXaSq4Aztpnmn Jdmol5zUVU0ErYXBh0gEoFYZphwWTwgnPiQi8tavRJWQzHNQ99duIzAU+/UCvy9cV5xaJFYY AEPx6//KJlVPYSpgyRf
  • Ironport-sdr: 6564a1bd_mp5XxOJ+070kMtt+ujrbd8dMBHmycJ3AZZJ7D1LIXuaLd39 Ig8MAADUDNKoyvvfG31utqpvzrkgGoA7caEjjHw==

Hello,

I'm trying to find a way to compute the trapezoidal decomposition of a simple polygon in linear time. Has Chazelle's algorithm (Chazelle, B.: Triangulating a simple polygon in linear time. Discrete Comput. Geom. 6(3), 485–524 (1991)) been implemented in CGAL? Or is there some other linear time algorithm that has been implemented? 

Thanks in advance



Archive powered by MHonArc 2.6.19+.

Top of Page