Intersection of paraboloids and application to Minkowski-type problems

DOI10.1145/2582112.2582153zbMATH Open1397.68212arXiv1403.0062OpenAlexW1998299495MaRDI QIDQ4635555FDOQ4635555

Pedro Machado Manhães de Castro, Boris Thibert, Quentin Mérigot

Publication date: 23 April 2018

Published in: Proceedings of the thirtieth annual symposium on Computational geometry (Search for Journal in Brave)

Abstract: In this article, we study the intersection (or union) of the convex hull of N confocal paraboloids (or ellipsoids) of revolution. This study is motivated by a Minkowski-type problem arising in geometric optics. We show that in each of the four cases, the combinatorics is given by the intersection of a power diagram with the unit sphere. We prove the complexity is O(N) for the intersection of paraboloids and Omega(N^2) for the intersection and the union of ellipsoids. We provide an algorithm to compute these intersections using the exact geometric computation paradigm. This algorithm is optimal in the case of the intersection of ellipsoids and is used to solve numerically the far-field reflector problem.

Full work available at URL: https://arxiv.org/abs/1403.0062

zbMATH Keywords

optimal transportpower diagramreflector problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Geometric optics (78A05)

Cited In (1)

• Convergence of a Newton algorithm for semi-discrete optimal transport

   Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Regular intersection of quadrics and parallel submanifolds 👍 👎
• APPLICATIONS OF AN INTERSECTION FORMULA TO DUAL CONES 👍 👎
• Intersection theorems and their applications in general almost convex spaces 👍 👎
• Minkowski's theorems on parallelohedra and their generalisations 👍 👎
• On convex intersection bodies and unique determination problems for convex bodies 👍 👎
• A generalization of intersection formulae of integral geometry 👍 👎
• Intersection theorems under dimension constraints 👍 👎
• Minkowski type problems for convex hypersurfaces in the sphere 👍 👎

This page was built for publication: Intersection of paraboloids and application to Minkowski-type problems

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