Distance-sensitive planar point location

详细信息    查看全文

• 作者：Boris Aronov^a ; ^{boris.aronov@nyu.edu" class="auth_mail" title="E-mail the corresponding author} ; Mark de Berg^b ; ^{mdberg@win.tue.nl" class="auth_mail" title="E-mail the corresponding author} ; David Eppstein^c ; ^{eppstein@ics.uci.edu" class="auth_mail" title="E-mail the corresponding author} ; Marcel Roeloffzen^d ; ^e ; ^{marcel@nii.ac.jp" class="auth_mail" title="E-mail the corresponding author} ; Bettina Speckmann^b ; ^{speckman@win.tue.nl" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Point location ; Quadtree ; Mesh generation
• 刊名：Computational Geometry
• 出版年：2016
• 出版时间：April 2016
• 年：2016
• 卷：54
• 期：Complete
• 页码：17-31
• 全文大小：517 K

文摘

Let class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0925772116300074&_mathId=si1.gif&_user=111111111&_pii=S0925772116300074&_rdoc=1&_issn=09257721&md5=9a37dda44302959c093c9440647922bf" title="Click to view the MathML source">Sclass="mathContainer hidden">class="mathCode">$\mathcal{S}$ be a connected planar polygonal subdivision with n   edges that we want to preprocess for point-location queries, and where we are given the probability class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0925772116300074&_mathId=si2.gif&_user=111111111&_pii=S0925772116300074&_rdoc=1&_issn=09257721&md5=b08c84cacb09856507300533f03466a9" title="Click to view the MathML source">γ_iclass="mathContainer hidden">class="mathCode">${\gamma }_i$ that the query point lies in a polygon class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0925772116300074&_mathId=si3.gif&_user=111111111&_pii=S0925772116300074&_rdoc=1&_issn=09257721&md5=321ff6feb1a8adf3872a75ededfe9c6d" title="Click to view the MathML source">P_iclass="mathContainer hidden">class="mathCode">$P_i$ of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0925772116300074&_mathId=si1.gif&_user=111111111&_pii=S0925772116300074&_rdoc=1&_issn=09257721&md5=9a37dda44302959c093c9440647922bf" title="Click to view the MathML source">Sclass="mathContainer hidden">class="mathCode">$\mathcal{S}$. We show how to preprocess class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0925772116300074&_mathId=si1.gif&_user=111111111&_pii=S0925772116300074&_rdoc=1&_issn=09257721&md5=9a37dda44302959c093c9440647922bf" title="Click to view the MathML source">Sclass="mathContainer hidden">class="mathCode">$\mathcal{S}$ such that the query time for a point class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0925772116300074&_mathId=si4.gif&_user=111111111&_pii=S0925772116300074&_rdoc=1&_issn=09257721&md5=7229333d9db3a4ec0a037edbbaa02653" title="Click to view the MathML source">p∈P_iclass="mathContainer hidden">class="mathCode">$p\in P_i$ depends on class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0925772116300074&_mathId=si2.gif&_user=111111111&_pii=S0925772116300074&_rdoc=1&_issn=09257721&md5=b08c84cacb09856507300533f03466a9" title="Click to view the MathML source">γ_iclass="mathContainer hidden">class="mathCode">${\gamma }_i$ and, in addition, on the distance from p   to the boundary of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0925772116300074&_mathId=si3.gif&_user=111111111&_pii=S0925772116300074&_rdoc=1&_issn=09257721&md5=321ff6feb1a8adf3872a75ededfe9c6d" title="Click to view the MathML source">P_iclass="mathContainer hidden">class="mathCode">$P_i$—the further away from the boundary, the faster the query. More precisely, we show that a point-location query can be answered in time class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0925772116300074&_mathId=si197.gif&_user=111111111&_pii=S0925772116300074&_rdoc=1&_issn=09257721&md5=618fa2cc5e38d17651d99cd529ceb5a0">class="imgLazyJSB inlineImage" height="35" width="197" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0925772116300074-si197.gif">class="mathContainer hidden">class="mathCode">$O(\min (\log n,1+\log \frac{\mathrm{area}(P_i)}{{\gamma }_i{\mathrm{\Delta }}_p^2}))$, where class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0925772116300074&_mathId=si49.gif&_user=111111111&_pii=S0925772116300074&_rdoc=1&_issn=09257721&md5=2ae763ee1f9f99b200d8e9b6a68e08a4" title="Click to view the MathML source">Δ_pclass="mathContainer hidden">class="mathCode">${\mathrm{\Delta }}_p$ is the shortest Euclidean distance of the query point p   to the boundary of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0925772116300074&_mathId=si3.gif&_user=111111111&_pii=S0925772116300074&_rdoc=1&_issn=09257721&md5=321ff6feb1a8adf3872a75ededfe9c6d" title="Click to view the MathML source">P_iclass="mathContainer hidden">class="mathCode">$P_i$. Our structure uses class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0925772116300074&_mathId=si76.gif&_user=111111111&_pii=S0925772116300074&_rdoc=1&_issn=09257721&md5=745501edadfef17b0583bd7cf5858db9" title="Click to view the MathML source">O(n)class="mathContainer hidden">class="mathCode">$O(n)$ space and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0925772116300074&_mathId=si47.gif&_user=111111111&_pii=S0925772116300074&_rdoc=1&_issn=09257721&md5=6ce5d80dcd541b26e264df38255f9bf1" title="Click to view the MathML source">O(nlog⁡n)class="mathContainer hidden">class="mathCode">$O(n\log n)$ preprocessing time. It is based on a decomposition of the regions of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0925772116300074&_mathId=si1.gif&_user=111111111&_pii=S0925772116300074&_rdoc=1&_issn=09257721&md5=9a37dda44302959c093c9440647922bf" title="Click to view the MathML source">Sclass="mathContainer hidden">class="mathCode">$\mathcal{S}$ into convex quadrilaterals and triangles with the following property: for any point class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0925772116300074&_mathId=si4.gif&_user=111111111&_pii=S0925772116300074&_rdoc=1&_issn=09257721&md5=7229333d9db3a4ec0a037edbbaa02653" title="Click to view the MathML source">p∈P_iclass="mathContainer hidden">class="mathCode">$p\in P_i$, the quadrilateral or triangle containing p   has area class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0925772116300074&_mathId=si10.gif&_user=111111111&_pii=S0925772116300074&_rdoc=1&_issn=09257721&md5=154e9902511e1bdefac941ca2442765b">class="imgLazyJSB inlineImage" height="19" width="43" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0925772116300074-si10.gif">class="mathContainer hidden">class="mathCode">$\mathrm{\Omega }({\mathrm{\Delta }}_p^2)$. For the special case where class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0925772116300074&_mathId=si1.gif&_user=111111111&_pii=S0925772116300074&_rdoc=1&_issn=09257721&md5=9a37dda44302959c093c9440647922bf" title="Click to view the MathML source">Sclass="mathContainer hidden">class="mathCode">$\mathcal{S}$ is a subdivision of the unit square and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0925772116300074&_mathId=si11.gif&_user=111111111&_pii=S0925772116300074&_rdoc=1&_issn=09257721&md5=1b3f78e7116d1075dc7246f75ebb962f" title="Click to view the MathML source">γ_i=area(P_i)class="mathContainer hidden">class="mathCode">${\gamma }_i=\mathrm{area}(P_i)$, we present a simpler solution that achieves a query time of class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0925772116300074&_mathId=si12.gif&_user=111111111&_pii=S0925772116300074&_rdoc=1&_issn=09257721&md5=88f0fa7de74f4ab797a1c50ee5dbe7bb">class="imgLazyJSB inlineImage" height="35" width="150" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0925772116300074-si12.gif">class="mathContainer hidden">class="mathCode">$O(\min (\log n,\log \frac{1}{{\mathrm{\Delta }}_p^2}))$. The latter solution can be extended to convex subdivisions in three dimensions.