An Efficient point-in-convex 3D polyhedron test using a projective algorithm with sub-linear expected complexity

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F25%3A43976476" target="_blank" >RIV/49777513:23520/25:43976476 - isvavai.cz</a>
Result on the web
<a href="https://link.springer.com/content/pdf/10.1007/s00138-025-01743-3.pdf" target="_blank" >https://link.springer.com/content/pdf/10.1007/s00138-025-01743-3.pdf</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s00138-025-01743-3" target="_blank" >10.1007/s00138-025-01743-3</a>

Result language
angličtina
Original language name
An Efficient point-in-convex 3D polyhedron test using a projective algorithm with sub-linear expected complexity
Original language description
We propose a novel algorithm for determining whether a given point lies within a convex polyhedron, achieving a sub-linear computational expected complexity of Oexp(N1/2), where N represents the number of triangles in the polyhedron’s triangular mesh. In contrast to traditional methods with linear complexity O(N), our approach significantly reduces com-putational overhead, making it especially effective for large polyhedral models. The algorithm is formulated entirely in projective space, utilizing homogeneous coordinates for the tested points and triangle vertices. By leveraging vector–vec¬tor operations optimized for SSE, AVX instructions, and GPU architectures, our method is robust and straightforward, tailored to handle even highly complex convex polyhedra. The efficiency of the approach was validated through theoretical analysis and estimated speed-up calculations, demonstrating its potential to accelerate applications in computer graphics, computational geometry, collision detection, and related fields. Additionally, the simplicity of the proposed algorithm ensures a high potential for broad applicability and supports further advancements in this area.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2025
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)