Finding simplices containing the origin in two and three dimensions

DOI10.1142/S0218195911003779MaRDI QIDQ5388706zbMATH OpenOpenAlexFDO

Authors Amr Elmasry, Kazuhisa Makino, Khaled Elbassioni

Publication date 19 April 2012

Published in International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0218195911003779

zbMATH Keywords

bichromatic problemscountingdivide and conquerenumerationoutput-sensitive algorithmssimplices

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• On Point Location and Motion Planning among Simplices
• Triangulating point sets in space
• On point location and motion planning among simplices
• Algorithms for a Minimum Volume Enclosing Simplex in Three Dimensions
• Algorithms for bichromatic line-segment problems and polyhedral terrains

Cites work

• Algorithm AS 307: Bivariate Location Depth
• Cutting hyperplanes for divide-and-conquer
• Finding the convex hull facet by facet
• Geometric medians
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• Lower bounds for computing statistical depth.
• On a triangle counting problem
• On enumerating minimal dicuts and strongly connected subgraphs
• Output-sensitive algorithms for computing nearest-neighbour decision boundaries
• Output-sensitive results on convex hulls, extreme points, and related problems
• Partitioning arrangements of lines. II: Applications
• The power of geometric duality
• The vertex set of a \(0/1\)-polytope is strongly \(\mathcal P\)-enumerable

Cited in

(4)

• Computing colourful simplicial depth and Median in \(\mathbb{R}_2\)
• Enumerating trichromatic triangles containing the origin in linear time
• On Combinatorial Depth Measures
• Hitting simplices with points in \(\mathbb R^{3}\)

Describes a project that uses

Uses Software

• AS 307

This page was built for publication: Finding simplices containing the origin in two and three dimensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5388706)