| Author | Title | Journal/Proceedings |
|---|---|---|
| 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 | To appear in 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: TO APPEAR |
||
| 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} } |
||