AuthorTitleJournal/Proceedings
David L. Millman
David P. Griesheimer
Brian R. Nease
Jack Snoeyink
Computing Numerically-Optimal Bounding Boxes for Constructive Solid Geometry (CSG) Components in Monte Carlo Transport Calculations SNA+MC 2013: Joint International Conference on Super Computing in Nuclear Applications + Monte Carlo 2013
Abstract: For large, highly detailed models, Monte Carlo simulations may spend a large fraction of their run-time performing simple point location and distance to surface calculations for every geometric component in a model. In such cases, the use of bounding boxes (axis-aligned boxes that bound each geometric component) can improve particle tracking efficiency and decrease overall simulation run time significantly. In this paper we present a robust and efficient algorithm for generating the numerically-optimal bounding box (optimal to within a user-specified tolerance) for an arbitrary Constructive Solid Geometry (CSG) object defined by quadratic surfaces. The new algorithm uses an iterative refinement to tighten an initial, conservatively large, bounding box into the numerically-optimal bounding box. At each stage of refinement, the algorithm subdivides the candidate bounding box into smaller boxes, which are classified as inside, outside, or intersecting the boundary of the component. In cases where the algorithm cannot unambiguously classify a box, the box is refined further. This process continues until the refinement near the component's extremal points reach the user-selected tolerance level. This refinement/classification approach is more efficient and practical than methods that rely on computing actual boundary representations or sampling to determine the extent of an arbitrary CSG component. A complete description of the bounding box algorithm is presented, along with a proof that the algorithm is guaranteed to converge to within specified tolerance of the true optimal bounding box. The paper also provides a discussion of practical implementation details for the algorithm as well as numerical results highlighting performance and accuracy for several representative CSG components.
BibTeX:
@inproceedings{mgns13_snamc,
   Author = {David L. Millman and David P. Griesheimer
         and Brian R. Nease and Jack Snoeyink},
   Booktitle = {SNA+MC 2013: Joint International Conference on
         Super Computing in Nuclear Applications + Monte Carlo},
   Note = {Electronic proceedings}
   Title = {Computing Numerically-Optimal Bounding Boxes for
         Constructive Solid Geometry ({CSG}) Components
         in {M}onte {C}arlo Transport Calculations},
   Year = {2013}
}
Brian R. Nease
David L. Millman
David P. Griesheimer
Daniel F. Gill
Geometric Templates for Improved Tracking Performance in Monte Carlo Codes SNA+MC 2013: Joint International Conference on Super Computing in Nuclear Applications + Monte Carlo 2013
Abstract: One of the most fundamental parts of a Monte Carlo code is its geometry kernel. This kernel not only affects particle tracking (i.e., run-time performance), but also shapes how users will input models and collect results for later analyses. A new framework based on geometric templates is proposed that optimizes performance (in terms of tracking speed and memory usage) and simplifies user input for large scale models. While some aspects of this approach currently exist in different Monte Carlo codes, the optimization aspect has not been investigated or applied. If Monte Carlo codes are to be realistically used for full core analysis and design, this type of optimization will be necessary. This paper describes the new approach and the implementation of two template types in MC21: a repeated ellipse template and a box template. Several different models are tested to highlight the performance gains that can be achieved using these templates. Though the exact gains are naturally problem dependent, results show that runtime and memory usage can be significantly reduced when using templates, even as problems reach realistic model sizes.
BibTeX:
@inproceedings{nmgg13_snamc,
   Author = {Brian R. Nease and David L. Millman
         and David P. Griesheimer and Daniel F. Gill},
   Booktitle = {SNA+MC 2013: Joint International Conference on
         Super Computing in Nuclear Applications + Monte Carlo},
   Note = {Electronic proceedings}
   Title = {Geometric Templates for Improved Tracking Performance in Monte Carlo Codes},
   Year = {2013}
}
David P. Griesheimer
et. al.
MC21 v.6.0 – A Continuous-Energy Monte Carlo Particle Transport Code with Integrated Reactor Feedback Capabilities SNA+MC 2013: Joint International Conference on Super Computing in Nuclear Applications + Monte Carlo 2013
Abstract: MC21 is a continuous-energy Monte Carlo radiation transport code for the calculation of the steady-state spatial distributions of reaction rates in three-dimensional models. The code supports neutron and photon transport in fixed source problems, as well as iterated-fission-source (eigenvalue) neutron transport problems. MC21 has been designed and optimized to support large-scale problems in reactor physics, shielding, and criticality analysis applications. The code also supports many in-line reactor feedback effects, including depletion, thermal feedback, xenon feedback, eigenvalue search, and neutron and photon heating. MC21 uses continuous-energy neutron/nucleus interaction physics over the range from 10−5 eV to 20 MeV. The code treats all common neutron scattering mechanisms, including fast-range elastic and non-elastic scattering, and thermal- and epithermal-range scattering from molecules and crystalline materials. For photon transport, MC21 uses continuous-energy interaction physics over the energy range from 1 keV to 100 GeV. The code treats all common photon interaction mechanisms, including Compton scattering, pair production, and photoelectric interactions. All of the nuclear data required by MC21 is provided by the NDEX system of codes, which extracts and processes data from EPDL-, ENDF-, and ACE-formatted source files. For geometry representation, MC21 employs a flexible constructive solid geometry system that allows users to create spatial cells from first- and second-order surfaces. The system also allows models to be built up as hierarchical collections of previously defined spatial cells, with interior detail provided by grids and template overlays. Results are collected by a generalized tally capability which allows users to edit integral flux and reaction rate information. Results can be collected over the entire problem or within specific regions of interest through the use of phase filters that control which particles are allowed to score each tally. The tally system has been optimized to maintain a high level of efficiency, even as the number of edit regions becomes very large.
BibTeX:
@inproceedings{mc2113_snamc,
   Author = {David P. Griesheimer and Daniel F. Gill and Brian R. Nease and
         Thomas M. Sutton and Mark H. Stedry and Peter S. Dobreff and
         David C. Carpenter and Timothy H. Trumbull and Ed Caro and
         Hansem Joo and Daivd L. Millman},
   Booktitle = {SNA+MC 2013: Joint International Conference on
         Super Computing in Nuclear Applications + Monte Carlo},
   Note = {Electronic proceedings},
   Title = {MC21 v.6.0 – A Continuous-Energy Monte Carlo Particle Transport Code
         with Integrated Reactor Feedback Capabilities},
   Year = {2013}
}
Brittany Terese Fasy
David L. Millman
Review of how to fold it by J. O'Rourke ACM SIGACT News 2013
Abstract: A review of a introductory text in computational geometry.
BibTeX:
@article{fm13_sigact,
   author = {Fasy, Brittany Terese and Millman, David L.},
   title = {Review of how to fold it by J. O'Rourke},
   journal = {SIGACT News},
   volume = {44},
   number = {3},
   month = {September},
   year = {2013},
   pages = {17--19},
   publisher = {ACM},
   address = {New York, NY, USA}
}
David L. Millman
Steven Love
Timothy M. Chan
Jack Snoeyink
Computing the Nearest Neighbor Transform Exactly with only Double Precision ISVD '12: Proceedings of the 9th Symposium on Voronoi Diagrams 2012
Abstract: The nearest neighbor transform of a binary image assigns to each pixel the index of the nearest black pixel – it is the discrete analog of the Voronoi diagram. Implementations that compute the transform use numerical calculations to perform geometric tests, so they may produce erroneous results if the calculations require more arithmetic precision than is available. Liotta, Preparata, and Tamassia, in 1999, suggested designing algorithms that not only minimize time and space resources, but also arithmetic precision. A simple algorithm using double precision can compute the nearest neighbor transform: compare the squared distances of each pixel to all black pixels, but this is inefficient when many pixels are black. We develop and implement efficient algorithms, computing the nearest neighbor transform of an image in linear time with respect to the number of pixels, while still using only double precision.
BibTeX:
@inproceedings{mlcs12_isvd,
   Author = {David L. Millman and Steven Love and
         Timothy M. Chan and Jack Snoeyink},
   Booktitle = {ISVD '12: Ninth International Symposium on
         Voronoi Diagrams in Science and Engineering (ISVD)},
   Pages = {66 - 74},
   Title = {Computing the Nearest Neighbor Transform Exactly with Only Double Precision},
   Year = {2012}
}
David L. Millman
David P. Griesheimer
Brian R. Nease
Jack Snoeyink
Robust Volume Calculations for Constructive Solid Geometry (CSG) Components in Monte Carlo Transport Calculations PHYSOR 2012: Advances in Reactor Physics 2012
Abstract: In this paper we consider a new generalized algorithm for the efficient calculation of component object volumes given their equivalent constructive solid geometry (CSG) definition. The new method relies on domain decomposition to recursively subdivide the original component into smaller pieces with volumes that can be computed analytically or stochastically, if needed. Unlike simpler brute-force approaches, the proposed decomposition scheme is guaranteed to be robust and accurate to within a user-defined tolerance. The new algorithm is also fully general and can handle any valid CSG component definition, without the need for additional input from the user. The new technique has been specifically optimized to calculate volumes of component definitions commonly found in models used for Monte Carlo particle transport simulations for criticality safety and reactor analysis applications. However, the algorithm can be easily extended to any application which uses CSG representations for component objects. The paper provides a complete description of the novel volume calculation algorithm, along with a discussion of the conjectured error bounds on volumes calculated within the method. In addition, numerical results comparing the new algorithm with a standard stochastic volume calculation algorithm are presented for a series of problems spanning a range of representative component sizes and complexities.
BibTeX:
@inproceedings{mgns12_physor,
   Author = {David L. Millman and David P. Griesheimer
         and Brian R. Nease and Jack Snoeyink},
   Booktitle = {PHYSOR 2012: Advances in Reactor Physics 2012},
   Note = {Electronic proceedings}
   Title = {Robust Volume Calculations for Constructive Solid Geometry ({CSG}) Components
         in {M}onte {C}arlo Transport Calculations},
   Year = {2012}
}
David L. Millman
Jack Snoeyink
Degree-Driven Algorithm Design for Computing Volumes of CSG Models Young Researchers Forum at CG Week 2012
Abstract: We describe a framework for computing volumes of CSG models. The framework was designed using Liotta, Preparata, and Tamassia’s degree-driven algorithm design paradigm, which suggests that the algorithm designer balances minimizing the time, space, and precision used by an algorithm. The framework serves as an example of how degree-driven algorithm design can be used in practice to produce a fast and accurate implementation.
BibTeX:
@inproceedings{m12_yrf,
   Author = {David L. Millman and Jack Snoeyink},
   Booktitle = {Young Researchers Forum at CG Week},
   Title = {Degree-Driven Geometric Algorithm Design for
         Computing Volumes of {CSG} Models},
   Year = {2012}
}
David L. Millman
Vishal Verma
A Slow Algorithm for Computing the Gabriel Graph with Double Precision CCCG '11: Proceedings of the 23rd Canadian Conference on Computational Geometry 2011
Abstract: When designing algorithms, time and space usage are commonly considered. In 1999, Liotta, Preparata and Tamassia proposed that we could also analyze the precision of an algorithm. We present our first steps towards the goal of efficiently computing the Gabriel graph of a finite set of sites, while restricting ourselves to only double precision.
BibTeX:
@inproceedings{mv11_cccg,
   Author = {David L. Millman and Vishal Verma},
   Pages = {485--487},
   Title = {A Slow Algorithm for Computing the Gabriel Graph with Double Precision},
   Url = {http://2011.cccg.ca/PDFschedule/papers/paper87.pdf},
   Year = {2011},
   booktitle = {Proceedings of the 23nd Canadian Conference on
         Computational Geometry (CCCG2011)}
}
David P. Griesheimer
David L. Millman
Clarence R. Willis
Analysis of distances between inclusions in finite binary stochastic materials Journal of Quantitative Spectroscopy and Radiative Transfer 2011
Abstract: A generalized probability density function (PDF) describing the distribution of inter-inclusion distances in finite, isotropic, binary stochastic materials with fixed diameter inclusions has been developed and tested. The new probability density function explicitly accounts for edge effects present in finite two- and three-dimensional stochastic materials. The generalized PDF is shown to include factors that are dependent on both the geometry of the material region as well as the statistical properties of the material. A discussion of the properties and application of this newly developed PDF is provided along with supporting numerical results for case studies in one- and two-dimensions. These numerical results demonstrate the ability of the newly derived PDF to correctly account for edge effects in finite stochastic materials, while still reproducing the expected distribution within the bulk material region.
BibTeX:
@article{gmw11_jqsrt,
   author = "David P. Griesheimer and David L. Millman and Clarence R. Willis",
   title = "Analysis of distances between inclusions in finite binary stochastic materials",
   journal = "Journal of Quantitative Spectroscopy and Radiative Transfer",
   volume = "112",
   number = "4",
   pages = "577 - 598",
   year = "2011",
   issn = "0022-4073",
   doi = "DOI: 10.1016/j.jqsrt.2010.06.013",
}
Brittany Terese Fasy
David L. Millman
Review of Geometric folding algorithms by authors: E.D. Demaine and J. O'Rourke ACM SIGACT News 2011
Abstract: A review of a graduate level text on the mathematics of linkages, origami and unfolding.
BibTeX:
@article{fm11_sigact,
   author = {Fasy, Brittany Terese and Millman, David L.},
   title = {Review of Geometric Folding Algorithms by authors:
                {E.D. D}emaine and {J}. {O}'{R}ourke},
   journal = {SIGACT News},
   volume = {42},
   number = {1},
   month = {March},
   year = {2011},
   pages = {43--46},
   publisher = {ACM},
   address = {New York, NY, USA}
}
Brittany Terese Fasy
David L. Millman
Review of Geometric algebra: An Algebraic System for Computer Games and Animation by J. Vince ACM SIGACT News 2011
Abstract: A review of an introductory text on geometric algebra.
BibTeX:
@article{fm11a_sigact,
   author = {Fasy, Brittany Terese and Millman, David L.},
   title = {Review of Geometric algebra: an algebraic system for computer games and
            animation by {J}. {V}ince}
   journal = {SIGACT News},
   volume = {42},
   number = {1},
   month = {March},
   year = {2011},
   pages = {46--48},
   publisher = {ACM},
   address = {New York, NY, USA}
}
Matthew O'Meara
David L. Millman
Jack Snoeyink
Vishal Verma
Maximum Geodesic Routing in the Plane with Obstacles CCCG '10: Proceedings of the 22nd Canadian Conference on Computational Geometry 2010
Abstract: Do convex obstacles in the plane always leave 3 separate escape routes? Here, an escape route is a locally geodesic path that avoids the obstacles; escape routes are separate if they have no point in common but their origin. We answer this question, posed at FWCG ’09 by Al-Jubeh, Ishaque and Tóth, in the affirmative and show how to efficiently compute the routes.
BibTeX:
@inproceedings{omsv10_cccg,
   Author = {Matthew O'Meara and David L. Millman and Jack Snoeyink and Vishal Verma},
   Pages = {107--108},
   Title = {Maximum Geodesic Routing in the Plane with Obstacles},
   Url = {http://cccg.ca/proceedings/2010/paper30.pdf},
   Year = {2010},
   booktitle = {Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010)},
}
David L. Millman,
Jack Snoeyink
Computing Planar Voronoi Diagrams in Double Precision: An Example of Degree-driven Algorithm Design SCG '10: Proceedings of the twenty-sixth annual Symposium on Computational Geometry 2010
Abstract: Geometric algorithms use numerical computations to perform geometric tests, so correct algorithms may produce erroneous results if insufficient arithmetic precision is available. Liotta, Preparata, and Tamassia, in 1999, suggested that algorithm design, which traditional considers running time and memory space, could also consider precision as a resource. They demonstrated that a Voronoi diagram of sites on a $U\times U$ grid could be rounded to answer "Post Office" queries on the same grid with only double precision, even though computing a Voronoi diagram requires the quadruple-precision InCircle test. We develop a similar rounded "Voronoi diagram" that can be computed directly using only double precision by randomized incremental construction in $O(n \log n\log U)$ expected time and $O(n)$ expected space. The structure produced can answer Post Office queries, which ask for the nearest site to a query on the grid, even though it doesn't even use sufficient precision to determine a Delaunay triangulation.
BibTeX:
@inproceedings{ms10_scg,
   author = {David L. Millman and Jack Snoeyink},
   title = {Computing planar Voronoi diagrams in double precision: a further example of
      degree-driven algorithm design},
   booktitle = {SCG '10: Proceedings of the 26th annual symposium on
      Computational geometry},
   year = {2010},
   isbn = {978-1-4503-0016-2},
   pages = {386--392},
   location = {Aarhus, Denmark},
   doi = {http://doi.acm.org/10.1145/1810959.1811024},
   publisher = {ACM},
   address = {New York, NY, USA},
}
Vicente H. F. Batista,
David L. Millman,
Sylvain Pion,
Johannes Singler
Parallel geometric algorithms for multi-core computers Computational Geometry: Theory and Applications 2010
Abstract: Computers with multiple processor cores using shared memory are now ubiquitous. In this paper, we present several parallel geometric algorithms that specifically target this environment, with the goal of exploiting the additional computing power. The algorithms we describe are (a) 2-/3-dimensional spatial sorting of points, as is typically used for preprocessing before using incremental algorithms, (b) d-dimensional axis-aligned box intersection computation, and finally (c) 3D bulk insertion of points into Delaunay triangulations, which can be used for mesh generation algorithms, or simply for constructing 3D Delaunay triangulations. For the latter, we introduce as a foundational element the design of a container data structure that both provides concurrent addition and removal operations and is compact in memory. This makes it especially well-suited for storing large dynamic graphs such as Delaunay triangulations. We show experimental results for these algorithms, using our implementations based on the Computational Geometry Algorithms Library (CGAL). This work is a step towards what we hope will become a parallel mode for CGAL, where algorithms automatically use the available parallel resources without requiring significant user intervention.
BibTeX:
@article{bmp10,
   Author = {Vicente H.F. Batista and David L. Millman and Sylvain Pion and Johannes Singler},
   Journal = {Computational Geometry},
   Number = {8},
   Pages = {663 - 677},
   Title = {Parallel geometric algorithms for multi-core computers},
   Volume = {43},
   Year = {2010}
}
Timothy M. Chan,
David L. Millman,
Jack Snoeyink
Discrete Voronoi Diagrams and Post Office Query Structures without the InCircle Predicate FWCG '09: Proceedings of the Nineteenth Annual Fall Workshop on Computational Geometry 2009
Abstract: We develop an algorithm to compute the Voronoi diagram (or distance transform) of $n$ sites (feature pixels) in a $U \times U$ grid using double precision, instead of the usualy 4-fold precision for the InCircle test. Our algorithm runs in $O(U^2 + n \log U )$ time.
BibTeX:
@inproceedings{cms09_fwcg,
   Author = {Timothy M. Chan and David L. Millman and Jack Snoeyink},
   Booktitle = {Proceedings of the Nineteenth Annual Fall Workshop on
         Computational Geometry},
   Pages = {33--34},
   Title = {Discrete {V}oronoi Diagrams and Post Office Query Structures
         without the InCircle Predicate},
   Year = {2009}
}
David L. Millman,
Jack Snoeyink
Computing the Reduced Voronoi Diagram in Triple Precision WADS '09: Proceedings of the Algorithms and Data Structure Symposium 2009
Abstract: In a paper that considered arithmetic precision as a limited resource in the design and analysis of algorithms, Liotta, Preparata and Tamassia defined an “implicit Voronoi diagram” supporting logarithmic-time proximity queries using predicates of twice the precision of the input and query coordinates. They reported, however, that computing this diagram uses five times the input precision. We define a reduced-precision Voronoi diagram that similarly supports proximity queries, and describe a randomized incremental construction using only three times the input precision. The expected construction time is O(n(log n + log \mu)), where \mu is the length of the longest Voronoi edge; we can construct the implicit Voronoi from the reduced-precision Voronoi in linear time.
BibTeX:
@inproceedings{ms09_wads,
   Author = {David L. Millman and Jack Snoeyink},
   Title = {Computing the Implicit {V}oronoi Diagram in Triple Precision},
   Booktitle = {Algorithms and Data Structures, 11th International Symposium,
      WADS 2009, Banff, Canada, August 21-23, 2009. Proceedings},
   Pages = {495-506},
   Publisher = {Springer},
   Series = {Lecture Notes in Computer Science},
   Volume = {5664},
   Year = {2009}
}
Brittany Terese Fasy
David L. Millman
Review of higher arithmetic: An Algorithmic Introduction to Number Theory by H. M. Edwards (American Mathematical Society Student Mathematical Library Vol. 45, 2008) ACM SIGACT News 2009
Abstract: This is a text in Number Theory with an algorithmic approach to the topic.
BibTeX:
@article{fm09_sigact,
   author = {Fasy, Brittany Terese and Millman, David L.},
   title = {Review of higher arithmetic: an algorithmic introduction to number theory by H. M. Edwards (American Mathematical Society Student Mathematical Library Vol. 45, 2008)},
   journal = {SIGACT News},
   volume = {40},
   number = {2},
   year = {2009},
   issn = {0163-5700},
   pages = {38--41},
   doi = {http://doi.acm.org/10.1145/1556154.1556165},
   publisher = {ACM},
   address = {New York, NY, USA}
}
Vicente H. F. Batista,
David L. Millman,
Sylvain Pion,
Johannes Singler
Parallel Geometric Algorithms for Multi-Core Computers SCG '09: Proceedings of the twenty-fifth annual Symposium on Computational Geometry 2009
Abstract: Computers with multiple processor cores using shared memory are now ubiquitous. In this paper, we present several parallel geometric algorithms that specifically target this environment, with the goal of exploiting the additional computing power. The d-dimensional algorithms we describe are (a) spatial sorting of points, as is typically used for preprocessing before using incremental algorithms, (b) kd-tree construction, (c) axis-aligned box intersection computation, and finally (d) bulk insertion of points in Delaunay triangulations for mesh generation algorithms or simply computing Delaunay triangulations. We show experimental results for these algorithms in 3D, using our implementations based on the Computational Geometry Algorithms Library (CGAL). This work is a step towards what we hope will become a parallel mode for CGAL, where algorithms automatically use the available parallel resources without requiring significant user intervention.
BibTeX:
@inproceedings{bmps09_scg,
   author = {Batista, Vicente H.F. and Millman, David L. and Pion, Sylvain and Singler, Johannes},
   title = {Parallel geometric algorithms for multi-core computers},
   booktitle = {SCG '09: Proceedings of the 25th annual symposium on
      Computational geometry},
   year = {2009},
   isbn = {978-1-60558-501-7},
   pages = {217--226},
   location = {Aarhus, Denmark},
   doi = {http://doi.acm.org/10.1145/1542362.1542404},
   publisher = {ACM},
   address = {New York, NY, USA},
}
David P. Griesheimer
David L. Millman
Analysis of Distances Between Inclusions in Finite One-dimensional Binary Stochastic Materials Proceedings of the International Conference on Mathematics, Computational Methods and Reactor Physics 2009
Abstract: In this paper we develop a statistical distribution for the number of inclusions present in a one- dimensional binary stochastic material of a finite length. From this distribution, an analytic solution for the expected number of inclusions present in a given problem is derived. For cases where the analytical solution for the expected number of inclusions is prohibitively expensive to compute, a simple, empirically-derived, approximation for the expected value is presented. A series of numerical experiments are used to bound the error of this approximation over the domain of interest. Finally, the above approximations are used to develop a methodology for determining the distribution of distances between adjacent inclusions in the material, subject to known problem conditions including: the total length of the problem, the length of each inclusion, and the expected volume fraction of inclusions in the problem. The new method is shown to be equivalent to the use of the infinite medium nearest neighbor distribution with an effective volume fraction to account for the finite nature of the material. Numerical results are presented for a wide range of problem parameters, in order to demonstrate the accuracy of this method and identify conditions where the method breaks down. In general, the technique is observed to produce excellent results (absolute error less than 10^-6) for problems with inclusion volume fractions less than 0.8 and a ratio of problem length to inclusion length greater than 25. For problems that do not fall into this category, the accuracy of the method is shown to be dependent on the particular combination of these parameters. A brief discussion of the relevance of this method for Monte Carlo chord length sampling algorithms is also provided.
BibTeX:
@inproceedings{gm09_mc,
   author = {David P. Griesheimer and David L. Millman},
   title = {Analysis of Distances Between Inclusions in Finite One-dimensional Binary Stochastic Materials},
   year = {2009},
   booktitle = {International Conference on Mathematics, Computational Methods and Reactor Physics (M\&C 2009)},
   note = {on CD-ROM},
   location = {Saratoga Springs, New York, USA},
   publisher = {American Nuclear Society},
   address = {LaGrange Park, IL, USA},
Vicente H. F. Batista,
David L. Millman,
Sylvain Pion,
Johannes Singler
Parallel Multi-Core Geometric Algorithms in CGAL Electronic Proceedings Workshop on Massively Multiprocessor and Multicore Computers 2009
Abstract: We describe an approach to efficiently use multiple processing cores and shared memory for several geometric algorithms. The d-dimensional algorithms we target are (a) spatial sorting of points, (b) kd-tree construction, (c) axis-aligned box intersection computation, and finally (d) bulk insertion of points in Delaunay triangulations. Underlying these comes also a thread-safe, efficient and memorywise compact container for storing dynamic geometric data structures. This work has been implemented in the framework of CGAL http://cgal.org/. We also show experimental results for these algorithms in the 3D case. This work is hopefully a step towards a parallel mode for CGAL, where algorithms automatically use the available parallel resources without requiring significant user intervention.
BibTeX:
@inproceedings{bmps09_wmmmc,
   author = {Vicente H. F. Batista and David L. Millman and Sylvain Pion and Johannes Singler},
   title = {Parallel Multi-Core Geometric Algorithms in {CGAL}},
   year = {2009},
   booktitle = {Workshop on Massively Multiprocessor and Multicore Computers},
   note = {electronic proceedings},
   url = {http://pagesperso-systeme.lip6.fr/Marc.Shapiro/multicoeurs-2009-02/}
}
Brittany Terese Fasy
David L. Millman
Review of Geometric algebra for computer science by Leo Dorst, Daniel Fontijne, and Stephen Mann (Morgan Kaufmann Publishers, 2007) ACM SIGACT News 2008
Abstract: Geometric Algebra for Computer Science by L. Dorst, D. Fontijne, and S. Mann. Review by B. Fasy and D. Millman. How can we view Geometry in terms that a computer can understand and deal with? This book helps answer that question.
BibTeX:
@article{fm08_sigact
   Address = {New York, NY, USA},
   Author = {Brittany Terese Fasy and David L. Millman},
   Doi = {http://doi.acm.org/10.1145/1466390.1466396},
   Issn = {0163-5700},
   Journal = {SIGACT News},
   Number = {4},
   Pages = {27--30},
   Publisher = {ACM},
   Title = {Review of Geometric algebra for computer science by Leo Dorst, Daniel Fontijne, and Stephen Mann (Morgan Kaufmann Publishers, 2007)},
   Volume = {39},
   Year = {2008},
}
Vicente H. F. Batista,
David L. Millman,
Sylvain Pion,
Johannes Singler
Parallel Geometric Algorithms for Multi-Core Computers INRIA Research Report 2008
Abstract: Computers with multiple processor cores using shared memory are now ubiquitous. In this paper, we present several parallel geometric algorithms that specifically target this environment, with the goal of exploiting the additional computing power. The d-dimensional algorithms we describe are (a) spatial sorting of points, as is typically used for preprocessing before using incremental algorithms, (b) kd-tree construction, (c) axis-aligned box intersection computation, and finally (d) bulk insertion of points in Delaunay triangulations for mesh generation algorithms or simply computing Delaunay triangulations. We show experimental results for these algorithms in 3D, using our implementations based on the Computational Geometry Algorithms Library (CGAL, http://www.cgal.org/). This work is a step towards what we hope will become a parallel mode for CGAL, where algorithms automatically use the available parallel resources without requiring significant user intervention.
BibTeX:
@techreport{geometrica-6749t,
   Author = {Vicente H. F. Batista and David L. Millman and Sylvain Pion and Johannes Singler},
   Institution = {INRIA},
   Number = 6749,
   Title = {Parallel Geometric Algorithms for Multi-Core Computers},
   Type = {Research Report},
   Url = {http://hal.inria.fr/inria-00343804/},
   Year = 2008,
}
David L. Millman,
Jack Snoeyink
Degree-driven algorithm design for computing the Voronoi diagram FWCG '08: Proceedings of the Eighteenth Annual Fall Workshop on Computational Geometry 2008
Abstract: The Voronoi diagram is the classic proximity query structure. It finds the nearest point from a finite set S to a given query point q and it is the partition of the plane into the maximal connected regions. The Voronoi diagram’s topological structure can be computed using four times the precision of the input, but representing its vertices requires five times the input precision. Furthermore, using the Voronoi diagram to solve proximity queries in O(log n) requires six times the precision of the input and query points. Liotta, Preparata, and Tamassia [3] have derived a structure from the Voronoi diagram whose computation requires five times the precision of the input, but which supports proximity queries in O(log n) time, using only two times the input precision. In this paper, we show how this structure can be computed directly, using at most triple precision in O(n(log n + log g)) time where g is the bisector length.
BibTeX:
@inproceedings{ms08,
   Author = {David L. Millman and Jack Snoeyink},
   Booktitle = {Proceedings of the Eighteenth Annual Fall Workshop on Computational Geometry},
   Pages = {20--21},
   Title = {Degree-driven algorithm design for computing the Voronoi diagram},
   Year = {2008}
}
David L. Millman Degeneracy Proof Predicates for the Additively Weighted Voronoi Diagram Masters Thesis, Courant Institute, New York University
Abstract: This thesis focuses on the Additively Weighted Voronoi diagram. It begins by presenting the history of the diagram and some of the early algorithms used for its generation [OBSC00, Aur91]. The paper then addresses the more recent incremental approach to calculating the diagram, as seen in the 2D Apollonius Graphs (Delaunay Graphs of Disks) package of CGAL [KY06]. Next, the algorithm of Boissonnat et al. [BD05] for calculating Convex Hulls is presented. We then apply the predicates presented by Bossonnat to the CGAL implementation of the AW-Voronoi diagram, and the results are discussed. The main contribution of this paper results in predicates of the AW-Voronoi diagram, with a lower algebraic degree which also handle degeneracies in such a way as to produce a conical result.
BibTeX:
@mastersthesis{m07_masters_thesis,
   Author = {David L. Millman},
   Month = {May},
   School = {Courant Institute, New York University},
   Title = {Degeneracy Proof Predicates for the Additively Weighted Voronoi Diagram},
   Year = {2007}
}