[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Far-field reflector problem and intersection of paraboloids

  • Published:
Numerische Mathematik Aims and scope Submit manuscript

Abstract

In this article, we propose a numerical approach to the far field reflector problem which is an inverse problem arising in geometric optics. Caffarelli et al. (Contemp Math 226:13–32, 1999) proposed an algorithm that involves the computation of the intersection of the convex hull of confocal paraboloids. We show that computing this intersection amounts to computing the intersection of a power diagram (a generalization of the Voronoi diagram) with the unit sphere. This allows us to provide an algorithm that computes efficiently the intersection of confocal paraboloids using the exact geometric computation paradigm. Furthermore, using an optimal transport formulation, we cast the far field reflector problem into a concave maximization problem. This allows us to numerically solve the far field reflector problem with up to 15k paraboloids. We also investigate other geometric optic problems that involve union of confocal paraboloids and also intersection and union of confocal ellipsoids. In all these cases, we show that the computation of these surfaces is equivalent to the computation of the intersection of a power diagram with the unit sphere.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

Notes

  1. We do not need orientation predicates at this point, since, in CGAL, 3-simplices of a triangulation are positively oriented.

References

  1. Aurenhammer, F.: Power diagrams: properties, algorithms and applications. SIAM J. Comput. 16, 78–96 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  2. Aurenhammer, F., Hoffmann, F., Aronov, B.: Minkowski-type theorems and least-squares clustering. Algorithmica 20(1), 61–76 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  3. Bertsekas, D.P., Eckstein, J.: Dual coordinate step methods for linear network flow problems. Math. Program. 42(1), 203–243 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  4. Boissonnat, J.-D., Karavelas, M.I.: On the combinatorial complexity of Euclidean Voronoi cells and convex hulls of d-dimensional spheres. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Philadelphia, PA, USA), SODA ’03. Society for Industrial and Applied Mathematics, pp. 305–312 (2003)

  5. Brónnimann, H., Burnikel, C., Pion, S.: Interval arithmetic yields efficient dynamic filters for computational geometry. Discret. Appl. Math. 109, 25–47 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  6. Caffarelli, L.A., Gutiérrez, C.E., Huang, Q.: On the regularity of reflector antennas. Ann. Math. Second Ser. 167(1), 299 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  7. Caffarelli, L.A., Kochengin, S., Oliker, V.I.: On the numerical solution of the problem of reflector design with given far-field scattering data. Contemp. Math. 226, 13–32 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  8. Caffarelli, L.A., Oliker, V.I.: Weak solutions of one inverse problem in geometric optics. J. Math. Sci. 154(1), 39–49 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  9. Cgal, Computational Geometry Algorithms Library. http://www.cgal.org

  10. Delage, C.: CGAL-based first prototype implementation of Möbius diagram in 2D. Technical Report ECG-TR-241208-01, INRIA Sophia-Antipolis, 2003

  11. Glimm, T., Oliker, V.: Optical design of single reflector systems and the Monge–Kantorovich mass transfer problem. J. Math. Sci. 117(3), 4096–4108 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  12. Guan, P., Wang, X.-J.: On a Monge–Ampere equation arising in geometric optics. J. Differ. Geom. 48(2), 205–223 (1998)

    MathSciNet  MATH  Google Scholar 

  13. Kettner, L., Mehlhorn, K., Schirra, S., Yap, C.K.: Classroom examples of robustness problems in geometric computations. Comput. Geom. Theory Appl. 40, 61–79 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  14. Kitagawa, J.: An iterative scheme for solving the optimal transportation problem (2012) (preprint). arXiv:1208.5172

  15. Kochengin, S.A., Oliker, V.I.: Determination of reflector surfaces from near-field scattering data. Inverse Probl. 13(2), 363 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  16. Mérigot, Q.: A multiscale approach to optimal transport. In: Computer Graphics Forum, vol. 30, pp. 1583–1592. Wiley Online Library, New York (2011)

  17. Mulmuley, K. (ed.): Computational geometry—an introduction through randomized algorithms. Prentice Hall, Englewood Cliffs (1994)

    MATH  Google Scholar 

  18. Oliker, V.I.: Mathematical aspects of design of beam shaping surfaces in geometrical optics. In: Trends in Nonlinear Analysis, pp. 193–224 (2003)

  19. Oliker, V.I.: A rigorous method for synthesis of offset shaped reflector antennas. Comput. Lett. 2(1–2), 1–2 (2006)

    Google Scholar 

  20. Oliker, V.I.: A characterization of revolution quadrics by a system of partial differential equations. Proc. Am. Math. Soc. 138(11), 4075–4080 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  21. Sack, J.-R., Urrutia, J. (eds.): Handbook of Computational Geometry. North-Holland Publishing Co., Amsterdam (2000)

    MATH  Google Scholar 

  22. Wang, X.J.: On the design of a reflector antenna ii. Calc. Var. Partial Differ. Equ. 20(3), 329–341 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  23. Wang, X.-J.: On the design of a reflector antenna. Inverse Probl. 12(3), 351 (1996)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

The authors would like to thank Dominique Attali, Olivier Devillers and Francis Lazarus for interesting discussions. Olivier Devillers suggested the approach used in the proof of the lower complexity bound for intersection of ellipsoids. P. M. M. de Castro is supported by Grant FACEPE/INRIA, APQ-0055-1.03/12. Q. Mérigot and B. Thibert would like to acknowledge the support of the French Agence Nationale de la Recherche (ANR) under reference ANR-11-BS01-014-01 (TOMMI) and ANR-13-BS01-0008-03 (TOPDATA) respectively.

Author information

Authors and Affiliations

  1. Centro de Informática, Universidade Federal de Pernambuco, Recife, Brazil

    Pedro Machado Manhães de Castro

  2. Université Grenoble Alpes, LJK, 38000, Grenoble, France

    Quentin Mérigot & Boris Thibert

  3. CNRS, LJK, 38000, Grenoble, France

    Quentin Mérigot & Boris Thibert

Authors
  1. Pedro Machado Manhães de Castro
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Quentin Mérigot
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Boris Thibert
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Boris Thibert.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

de Castro, P.M.M., Mérigot, Q. & Thibert, B. Far-field reflector problem and intersection of paraboloids. Numer. Math. 134, 389–411 (2016). https://doi.org/10.1007/s00211-015-0780-z

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00211-015-0780-z

Mathematics Subject Classification

Search

Navigation