Nina Amenta's Publications

Shengren Li and Nina Amenta,
Brute-force k-nearest neighbors search on the GPU,
Proceedings of Similarity Search and Applications, Volume 9371, Lecture Notes in Computer Science, Springer, pp 259-270, 2015.

Melissa Tallman, Nina Amenta, Eric Delson, Stephen R. Frost, Deboshmita Ghosh, Zachary S. Klukkert, Andrea Morrow and Gary J. Sawer,
Evaluation of a new method of fossil retrodeformation by algorithmic symmetrization: crania of Papionins (Primates, Cercopithecidae) as a test case,
PLoS One, 2014.

Stewart He and Nina Amenta, LiDAR Point Cloud Analysis using 3D Shape Descriptors,
ForestSAT, poster, 2014.

Carlos Rojas, Alex Tsui, Stewart He, Lance Simons, Shengren Li and Nina Amenta,
Edge length interpolation,
ACM Symposium on Solid and Physical Modeling, poster paper, 2014.

Lance Simons, Stewart He, Peter Tittmann, and Nina Amenta,
Point-based rendering of forest LiDAR,
Workshop on Visualization in Environmental Sciences, 2014.

Zehra Shah, Stewart He, Peter Tittmann, and Nina Amenta,
Analysis of airborne laser scanning data with regional shape descriptors,
Proceedings of SilviLaser, 2013. Oral presentation.

Alex Tsui, Devin Fenton, Phong Vuon, Joel Hass, Nina Amenta, David Coeurjolly, Charles DeCarli and Owen Carmichael,
Globally optimal cortical surface matching with exact landmark correspondence,
Proceedings of Information Processing in Medical Imaging, pages 487-498, 2013.

Fatemeh Abbasinejad, Pushkar Joshi, Cindy Grimm, Nina Amenta, Lance Simons.
Surface patches for 3D sketching,
Proceedings of the International Symposium on Sketch-Based Interfaces and Modeling, 2013.

Shengren Li, Lance Simons, Jagadeesh Bhaskar Pakaravoor, Fatemeh Abbasinejad, John D. Owens and Nina Amenta,
kANN on the GPU with Shifted Sorting,
Proceedings of High Performance Graphics, 2012.

Nina Amenta, Dominique Attali, Olivier Devillers,
A Tight Bound for the Delaunay Triangulation of Points on a Polyhedron,
Discrete and Computational Geometry 48(1), pages 19-38, 2012.

Dan A. Alcantara, Vasily Volkov, Shubharbarata Sengupta, Michael Mitzenmacher, John D. Owens and Nina Amenta.
Building an efficient hash table on the GPU,
in GPU Computing Gems (Jade edition), Wen-Mei W. Hwa, editor, Morgan Kaufman, pages 39-53, 2012.

Shengyin Gu, Patrice Koehl, Joel Hass, and Nina Amenta.
Surface-histogram: A new shape descriptor for protein-protein docking,
Proteins: Structure, Function and Bioinformatics, 80:1, Pages 221-238, 2011.

Fatemeh Abbasinejad, Pushkar Joshi, and Nina Amenta.
Surface Patches from Unorganized Space Curves,
Computer Graphics Forum (Proceedings of SGP), 30:5 pages 1379-1387, 2011.

Patricia Francis-Lyon, Shengyin Gu, Joel Hass, Nina Amenta and Patrice Koehl.
Sampling the conformation of protein surface residues for flexible protein docking,
BMC Bioinformatics 11:575, 2010.

Eric Perlman, Randal Burns, Michael Kazhdan, Rebecca R. Murphy, William P. Ball, and Nina Amenta,
Organization of data in non-convex spatial domains,
Scientific and statistical database management (SSDBM) pages 342-359, 2010.

Deboshmita Ghosh, Nina Amenta, Michael M. Kazhdan.
Closed-form Blending of Local Symmetries,
Computer Graphics Forum, (Proceedings of SGP 2010), 29:5, pages 1681-1688, 2010.

Dan A. Alcantara, Andrei Sharf, Fatemeh Abbasinejad, Shubhabrata Sengupta, Michael Mitzenmacher, John D. Owens, and Nina Amenta
Real-time parallel hashing on the GPU,
ACM Transactions on Graphics, (Proceedings of ACM SIGGRAPH Asia 2009)

Misha Kazhdan, Nina Amenta, Shengyin Gu, David F. Wiley and Bernd Hamann.
Symmetry restoration by stretching,
Canadian Computational Geometry Conference, 2009.

Dan A. Alcantara, Owen Carmichael, Eric Delson, Will Harcourt-Smith, Kirsten Sterner, Stephen Frost, Rebecca Dutton, Paul Thompson, Howard Aizenstein, Oscar Lopez, James Becker, and Nina Amenta.
Exploration of Shape Variation Using Localized Components Analysis ,
IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 2009, 31:8 pages 1510--1516.

Fatemeh Abbasinejad, Yong J. Kil, Andrei Sharf and Nina Amenta
Rotating scans for systematic error removal ,
Eurographics Symposium on Geometry Processing, 2009.
Awarded 2nd Best Paper

Deboshmita Ghosh, Andrei Sharf, and Nina Amenta.
Feature-driven deformation for dense correspondence,
Proceedings of SPIE Medical Imaging, pages 36--40, , vol. 7261, 2009.

Andrei Sharf, Dan A. Alcantara, Thomas Lewiner, Chen Greif, Alla Sheffer, Nina Amenta, and Daniel Cohen-Or.
Space-time surface reconstruction using incompressible flow,
SIGGRAPH ASIA, Article No. 110, 2008.

Yong J Kil and Nina Amenta.
GPU-assisted Surface Reconstruction on Locally-uniform Samples
Proceedings of International Meshing Roundtable, pages 369-385, 2008.

Dan A. Alcantara, Owen Carmichael, Eric Delson, Will Harcourt-Smith, Kirsten Sterner, Stephen Frost, Rebecca Dutton, Paul Thompson, Howard Aizenstein, Oscar Lopez, James Becker, and Nina Amenta.
Localized Components Analysis ,
Proceedings of Information Processing in Medical Imaging, Lecture Notes in Computer Science, Vol 4584, 2007, pages 519-531.

Nina Amenta, Dominique Attali and Olivier Devillers.
Complexity of Delaunay triangulation for points on lower-dimensional polyhedra,
ACM-SIAM Sympoisum on Discrete Algorithms (SODA), 2007, pages 1106-1113.

Shengyin Gu, Iain Anderson, Victor Kunin, Michael J. Cipriano, Simon Minovitsky, Gunther H. Weber, Nina Amenta, Bernd Hamann, and Inna Dubchak. TreeQ-VISTA: an interactive tree visualization tool with functional annotation query capabilities,
Bioinformatics 23(6): 764-766 (2007)

Nina Amenta, Matthew Godwin, Nicolay Postarnakevich, and Katherine St. John
Approximating geodesic tree distance,
Information Processing Letters, 103:2, 2007, pages 61--65.

Maria Bonet, Katherine St. John, Ruchi Mahindru and Nina Amenta.
Approximating subtree distances between phylogenies,
Journal of Computational Biology, 13(8): 1419-1434, 2006.

Yong Joo Kil, Boris Mederos and Nina Amenta
Laser Scanner Super-resolution,
Eurographics Workshop on Point-based Graphics, 2006, pages 9--16.
An abstract of a slightly earlier version of this work also appeared as:
Combining Laser Scans,
Sketch abstract, SIGGRAPH, 2006.

David F. Wiley, Nina Amenta, Dan A. Alcantara, Deboshmita Ghosh, Yong J. Kil, Eric Delson, Will Harcourt-Smith, F. James Rohlf, Katherine St. John, and Bernd Hamann. Evolutionary Morphing, Proceedings of IEEE Visualization, 2005, pages 431-438.

Boris Mederos, Nina Amenta, Luiz Vehlo and Luiz Henrique de Figueiredo
Surface reconstruction from noisy point clouds, Eurographics Symposium on Geometry Processing, 2005, pages 53-62.

Nina Amenta and Yong Joo Kil
The domain of a point-set surface,
Eurographics Workshop on Point-based Graphics, 2004, pages 139--147

Nina Amenta and Yong Kil. Defining point-set surfaces, SIGGRAPH 2004, pages 264-270. Quicktime movie explaining extremal surfaces, which we show in the paper are related to popular point-set surface constructions, by Lok Hwa, Yong Kil, Nina Amenta and John Liechty. Warning! Part of Claim 1 is incorrect. Thanks to Shlomo Gortler and (undergrad!) Zachary Abel for pointing out the problem. See the following short write-up: Nina Amenta. Minima and Saddles in the MLS Surface Definition, Erratum, 2008

Nina Amenta, Frederic Clarke and Katherine St. John.
A randomized linear-time majority tree algorithm, short paper, European Conference on Compuational Biology, 2003, poster proceedings.

Nina Amenta, Frederick Clarke and Katherine St. John.
A linear-time majority tree algorithm, Workshop on Algorithms in Bio-informatics, 2003, pages 216-227, Lecture Notes in Computer Science.

Nina Amenta, Sunghee Choi, and Guenter Rote.
Incremental constructions con BRIO
ACM Symposium on Computational Geometry, 2003, pages 211-219

Nina Amenta and Sunghee Choi
Blocked randomized incremental constructions
UT Technical Report Number TR-02-54, 2002

Nina Amenta, Sunghee Choi, Maria E. Jump, Ravi Krishna Kolluri and Thomas Wahl.
Finding alpha-helices in skeletons
UT Technical Report Number TR-02-27, 2002

Jeff Klingner and Nina Amenta.
Case Study: Visualization of Evolutionary Trees,
Case study, IEEE Information Visualization, 2002, pages 71--74.

Nina Amenta, Thomas J. Peters, and Alexander Russell.
Computational Topology: Ambient Isotopic Approximation of 2-Manifolds,
Theoretical Computer Science, to appear.

Sunghee Choi and Nina Amenta.
Delaunay triangulation programs on surface data,
The 13th ACM-SIAM Symposium on Discrete Algorithms, 2002, pages 135-136.

Nina Amenta, Sunghee Choi and Ravi Kolluri. The Power Crust, Proceedings of 6th ACM Symposium on Solid Modeling, 2001, pages 249-260.

Nina Amenta, Sunghee Choi and Ravi Kolluri.
The power crust, unions of balls, and the medial axis transform,
Computational Geometry: Theory and Applications, 2001, 19:(2-3), pages 127-153.

Nina Amenta and Ravi Kolluri.
The medial axis of a union of balls,
Computational Geometry: Theory and Applications, 20:(1-2), pages pp. 25-37, 2001.
An earlier version appeared in the 12th Canadian Conference on Computational Geometry, 2000, pages 111-114.

Nina Amenta and Ravi Kolluri.
Accurate and efficient unions of balls,
ACM Symposium on Computational Geometry, 2000, pages 119-128.

Nina Amenta, Sunghee Choi, Tamal Dey and Naveen Leekha.
A simple algorithm for homeomorphic surface reconstruction
ACM Symposium on Computational Geometry, 2000, pages 213-222.
submitted to the International Journal of Computational Geometry and its Applications

Nina Amenta, Marshall Bern, David Eppstein and Shang-Hua Teng.
Regression depth and center points,
Discrete and Computational Geometry, 23(3):305-323, (2000), pages 305-323.

Nina Amenta and Sunghee Choi.
One-Pass Delaunay filtering for homeomorphic 3D surface reconstruction,
UT Technical report number TR99-08 (1999)

Nina Amenta and Günter Ziegler.
Deformed products and maximal shadows of polytopes.
in: Advances in Discrete and Computational Geometry, (B. Chazelle, J.E. Goodman, R. Pollack, eds.), Contemporary Mathematics 223 (1999), Amer. Math. Soc., Providence, 57-90.

I am one of many authors of the Report of the NSF Workshop on Computational Topology,
Emerging Challanges in Computational Topology

Nina Amenta, Marsahll Bern and Manolis Kamvysselis. A new Voronoi-based surface reconstruction algorithm, Siggraph '98, pages 415-421 (1998).

Nina Amenta and Marshall Bern.
Surface reconstruction by Voronoi filtering,
Discrete and Computational Geometry, 22, pages 481-504, (1999).
An earlier version appeared in the
14th Annual ACM Symposium on Computational Geometry, pages 39-48, (1998).

Warning! The proof for Lemma 2 is incorrect. This is the lemma concerning how quickly the surface normal can change as a function of local feature size. Fortunately, Tamal Dey and I have come up with an alternative proof, which actually provides a better bound. So any subsequent work which applies this lemma is still correct, possibly with a better constant! Thanks to Jian Sun and Siu-Wing Cheng for pointing out the problem. The new proof is in the following document.

Nina Amenta and Tamal K. Dey.
Normal variation for adaptive feature size ,
Erratum, 2007

Nina Amenta, Marshall Bern and David Eppstein.
The crust and the beta-skeleton: combinatorial curve reconstruction,
Graphical Models and Image Processing, 60/2:2, pages 125-135 (1998).

Nina Amenta, Marshall Bern and David Eppstein.
Optimal point placement for mesh smoothing,
Journal of Algorithms 30 (1999) pages 302-322. An earlier version appreared in the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, (1997).

Nina Amenta.
Software, Chapter 52 of the CRC Handbook of Discrete and Computational Geometry,
CRC Press, Goodman and O'Rourke, eds. (1997), pages 951-960.
Most of this material appears in my online Directory of Computational Geometry Software.

Nina Amenta and Günter Ziegler.
Shadows and slices of polytopes,
Proceedings of the 12th Annual ACM Symposium on Computational Geometry, pages 10-19, (1996).

I am one of the many authors of the Computational Geometry Impact Task Force Report,
Application Challanges to Computational Geometry, (1996)

Pankaj Agarwal, Nina Amenta and Micha Sharir.
Largest placement of one convex polygon inside another,
Discrete and Computational Geometry, 19:95-104 (1998).
Another version appeared in the
2nd International Workshop on the Algorithmic Foundations of Robotics (1996).

Nina Amenta.
A new proof of an interesting Helly-type theorem
Discrete and Computational Geometry, 15:423-427 (1996).

Nina Amenta.
k-Transversals of parallel convex sets,
Proceedings of the Canadian Computational Geometry Conference, (1996), pages 80-86.

Nina Amenta, editor.
Proceedings of the International Computational Geometry Software Workshop,
Geometry Center Research Report GCG-80 (1995)

Nina Amenta, Stuart Levy, Tamara Munzner and Mark Phillips.
Geomview: a system for geometric visualization,
communication to the Proceedings of the 11th Annual ACM Symposium on Computational Geometry (1995) pp C12-13.

Nina Amenta.
Bounded boxes, Hausdorff distance, and a new proof of an interesting Helly-type theorem,
Proceedings of the 10th Annual ACM Symposium on Computational Geometry (1994) pages 340-347.

Nina Amenta.
Helly theorems and generalized linear programming,
Discrete and Computational Geometry 12:3 (1994) pages 241-261. Special issue.
An earlier version appeared in the Proceedings of the 9th Annual ACM Symposium on Computational Geometry, (1993) pages 63-72.

Nina Amenta.
Helly Theorems and Generalized Linear Programming,
PhD Thesis, U.C. Berkeley,
Geometry Center Preprint number 61.

Nina Amenta.
Finding a line transversal of axial objects in three dimensions,
Proceeding of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms, (1992) pages 66-71.