David F. Wiley, Nina Amenta, Dan A. Alcantara, Deboshmita Ghosh, Yong J. Kil, Eric Delson, ...
We introduce a technique to visualize the gradual evolutionary change of the shapes of living things as a morph between known three-dimensional shapes. Given geometric computer models of anatomical...
Approximating subtree distances between phylogenies (2009)
Maria Luisa Bonet, Katherine St. John, Ruchi Mahindru, Nina Amenta
We give a 5-approximation algorithm to the rooted Subtree-Prune-and-Regraft (rSPR) distance between two phylogenies, which was recently shown to be NP-complete. This paper presents the first...
Abstract A New Voronoi-Based Surface Reconstruction Algorithm (2009)
We describe our experience with a new algorithm for the reconstruction of surfaces from unorganized sample points in ¢£¥ ¤. The algorithm is the first for this problem with provable guarantees....
Abstract A New Voronoi-Based Surface Reconstruction Algorithm (2008)
We describe our experience with a new algorithm for the reconstruction of surfaces from unorganized sample points in IR 3.Thealgorithm is the first for this problem with provable guarantees. Given a...
Abstract A New Voronoi-Based Surface Reconstruction Algorithm (2008)
We describe our experience with a new algorithm for the reconstruction of surfaces from unorganized sample points inIR3. The algorithm is the first for this problem with provable guarantees. Given a...
Regression depth and center points (2008)
Nina Amenta, Marshall Bern, Shang-hua Teng
We show that, for any set of n points in d dimensions, there exists a hyperplane with regression depth at least ⌈n/(d + 1)⌉, as had been conjectured by Rousseeuw and Hubert. Dually, for any...
Abstract Defining Point-Set Surfaces (2008)
The MLS surface [Levin 2003], used for modeling and rendering with point clouds, was originally defined algorithmically as the output of a particular meshless construction. We give a new explicit...
Harris, Peter, Alcantara, Dan A, Amenta, Nina, Lopez, Oscar L, EirÃksdóttir, Guðný, Sigurðsson, Sigurður, ...
Hypertension is highly prevalent in elderly individuals and may be associated with cognitive decline, but the mechanisms by which hypertension may impact brain structure, and thereby modulate the...
A Tight Bound for the Delaunay Triangulation of Points on a Polyhedron (2008)
Amenta, Nina, Attali, Dominique, Devillers, Olivier
We show that the Delaunay triangulation of a set of n points distributed nearly uniformly on a p-dimensional polyhedron (not necessarily convex) in d-dimensional Euclidean space is O(n^((d-k+1)/p)),...
A Tight Bound for the Delaunay Triangulation of Points on a Polyhedron (2008)
Amenta, Nina, Attali, Dominique, Devillers, Olivier
We show that the Delaunay triangulation of a set of n points distributed nearly uniformly on a p-dimensional polyhedron (not necessarily convex) in d-dimensional Euclidean space is O(n^((d-k+1)/p)),...
Shengyin Gu, Iain Anderson, Victor Kunin, Michael Cipriano, Simon Minovitsky, Nina Amenta, ...
Summary: We describe a general multiplatform exploratory tool called TreeQ-Vista, designed for presenting functional annotations in a phylogenetic context. Traits, such as phenotypic and genomic...
A Randomized Linear-time Majority Tree Algorithm (2008)
Nina Amenta, Frederick Clarke, Katherine St. John
We give a randomized linear-time algorithm for computing the majority tree, a technique widely used for summarizing sets of phylogenetic trees. We are implementing the algorithm as part of an...
Localized Components Analysis (2008)
Dan Alcantara, Owen Carmichael, Will Harcourt-smith, Kirsten Sterner, Stephen Frost, Rebecca Dutton, ...
Abstract. We introduce Localized Components Analysis (LoCA) for describing surface shape variation in an ensemble of biomedical objects using a linear subspace of spatially localized shape...
Shengyin Gu, Iain Anderson, Victor Kunin, Michael Cipriano, Simon Minovitsky, Nina Amenta, ...
Summary: We describe a general multiplatform exploratory tool called TreeQ-Vista, designed for presenting functional annotations in a phylogenetic context. Traits, such as phenotypic and genomic...
Abstract Accurate and Efficient Unions of Balls (2008)
Given a sample of points from the bound-ary of an object in IR 3, we construct a rep-resentation of the object as a union of balls. We use many fewer balls than previous con-structions, but our shape...
Abstract Defining Point-Set Surfaces (2008)
The MLS surface [Levin 2003], used for modeling and rendering with point clouds, was originally defined algorithmically as the output of a particular meshless construction. We give a new explicit...
Surface Reconstruction from Noisy Point Clouds (2008)
M. Desbrun, H. Pottmann (editors, Boris Mederos, Nina Amenta, Luiz Velho
We show that a simple modification of the power crust algorithm for surface reconstruction produces correct outputs in presence of noise. This is proved using a fairly realistic noise model. Our...
Yong Joo Kil, Boris Mederos, Nina Amenta
Figure 1: Left, a patch of a single surface captured by a laser range scanner at about.4mm/sample. Center, we integrate many of these surfaces to create a single high-quality surface on a...
Surface Reconstruction from Noisy Point Clouds (2008)
M. Desbrun, H. Pottmann (editors, Boris Mederos, Nina Amenta, Luiz Velho
We show that a simple modification of the power crust algorithm for surface reconstruction produces correct outputs in presence of noise. This is proved using a fairly realistic noise model. Our...
Abstract Complexity of Delaunay triangulation for points on lower-dimensional polyhedra (2008)
We show that the Delaunay triangulation of a set of points distributed nearly uniformly on a polyhedron (not necessarily convex) of dimension p in d-dimensional space is O(n (d−1)/p). For all 2 ≤...
Abstract A New Voronoi-Based Surface Reconstruction Algorithm (2008)
We describe our experience with a new algorithm for the reconstruction of surfaces from unorganized sample points in ¢£¥ ¤. The algorithm is the first for this problem with provable guarantees....
Laser Scanner Super-resolution (2008)
M. Botsch, B. Chen (editors, Yong Joo Kil, Boris Mederos, Nina Amenta
We give a method for improving the resolution of surfaces captured with a laser range scanner by combining many very similar scans. This idea is an application of the 2D image processing technique...
General Terms Algorithms (2008)
Randomized incremental constructions are widely used in computational geometry, but they perform very badly on large data because of their inherently random memory access patterns. We define a biased...
A Tight Bound for the Delaunay Triangulation of Points on a Polyhedron (2008)
Amenta, Nina, Attali, Dominique, Devillers, Olivier
We show that the Delaunay triangulation of a set of n points distributed nearly uniformly on a p-dimensional polyhedron (not necessarily convex) in d-dimensional Euclidean space is O(n^((d-k+1)/p)),...
A Tight Bound for the Delaunay Triangulation of Points on a Polyhedron (2008)
Amenta, Nina, Attali, Dominique, Devillers, Olivier
We show that the Delaunay triangulation of a set of n points distributed nearly uniformly on a p-dimensional polyhedron (not necessarily convex) in d-dimensional Euclidean space is O(n^((d-k+1)/p)),...
Abstract Submitted to Solid Modeling ’00 The Power Crust (2007)
Nina Amenta, Sunghee Choi, Ravi Krishna Kolluri
Figure 1. Laser range data, the reconstructed watertight polygonal model, and its simplified medial axis. The power crust is a construction which takes a sample of points from the surface of a...
Discrete And Computational Geometry: Ten Years Later (2007)
Bernard Chazelle, J Anos Pach, Pankaj K. Agarwal, Nina Amenta
.77> O(f 2 ) vertices. The (incorrect) conjecture of the title is that o(f 2 ) of these vertices can appear on the outer boundary of a projection to the plane (a "shadow"). The video...
Finding -helices in skeletons (2007)
Nina Amenta, Sunghee Choi, Maria E. Jump, Ravi Krishna Kolluri, Thomas Wahl
We consider a problem which is part of the process of determining the three-dimensional structure of a protein molecule using X-ray crystallography: given an estimated map of the electron density of...
Nina Amenta, Ravi Krishna Kolluri
We present an algorithm for computing the exact interior medial axis of a union of balls in IR d. Our algorithm combines the simple characterization of this medial axis given by Attali and Montanvert...
General Terms Algorithms (2007)
Randomized incremental constructions are widely used in computational geometry, but they perform very badly on large data because of their inherently random memory access patterns. We define a biased...
can be divided into a union of parallel (d\Gammak)-flats of the form x 1 = g 1; x 2 = g 2; : : : x k = g k, where the g i are constant. Let C be a family of parallel (d \Gamma k)-dimensional convex...
Abstract The Power Crust (2007)
Nina Amenta, Sunghee Choi, Ravi Krishna Kolluri
Figure 1. Laser range data, the reconstructed watertight polygonal model, and its simplified medial axis. The power crust is a construction which takes a sample of points from the surface of a...
Nina Amenta, Marshall Bern, Manolis Kamvysselis
We describe our experience with a new algorithm for the reconstruction of surfaces from unorganized sample points in IR 3. The algorithm is the first for this problem with provable guarantees. Given...
Complexity of Delaunay Triangulation for Points on Lower-dimensional~Polyhedra (2007)
Amenta, Nina, Attali, Domiique, Devillers, Olivier
We show that the Delaunay triangulation of a set of points distributed nearly uniformly on a polyhedron (not necessarily convex) of dimension p in d-dimensional space is O(n^(d-1)/p))$. For all p...
Complexity of Delaunay Triangulation for Points on Lower-dimensional~Polyhedra (2007)
Amenta, Nina, Attali, Domiique, Devillers, Olivier
We show that the Delaunay triangulation of a set of points distributed nearly uniformly on a polyhedron (not necessarily convex) of dimension p in d-dimensional space is O(n^(d-1)/p))$. For all p...
Gu, Shengyin, Anderson, Iain, Kunin, Victor, Cipriano, Michael, Minovitsky, Simon, Weber, Gunther, ...
Summary: We describe a general multiplatform exploratory tool called TreeQ-Vista, designed for presenting functional annotations in a phylogenetic context. Traits, such as phenotypic and genomic...
Gu, Shengyin, Anderson, Iain, Kunin, Victor, Cipriano, Michael, Minovitsky, Simon, Weber, Gunther, ...
Summary: We describe a general multiplatform exploratory tool called TreeQ-Vista, designed for presenting functional annotations in a phylogenetic context. Traits, such as phenotypic and genomic...
Complexity of Delaunay Triangulation for Points on Lower-dimensional~Polyhedra (2007)
Amenta, Nina, Attali, Dominique, Devillers, Olivier
We show that the Delaunay triangulation of a set of points distributed nearly uniformly on a polyhedron (not necessarily convex) of dimension p in d-dimensional space is O(n^(d-1)/p))$. For all p...
Complexity of Delaunay Triangulation for Points on Lower-dimensional~Polyhedra (2007)
Amenta, Nina, Attali, Dominique, Devillers, Olivier
We show that the Delaunay triangulation of a set of points distributed nearly uniformly on a polyhedron (not necessarily convex) of dimension p in d-dimensional space is O(n^(d-1)/p))$. For all p...
Complexity of Delaunay triangulation for points on lower-dimensional polyhedra (2007)
Thème Sym, Nina Amenta, Nina Amenta, Dominique Attali, Dominique Attali, Olivier Devillers, ...
apport de recherche ISSN 0249-6399 ISRN INRIA/RR--5986--FR+ENG Complexity of Delaunay triangulation for points on lower-dimensional polyhedra
Background Normal variation for adaptive feature size (2007)
Tamal K. Dey, Nina Amenta, Tamal K. Dey
paper [4] is wrong. A correct proof with an improved bound is given at the end of this erratum.
Definitions and Preliminaries (2007)
Let Σ be a closed, smooth surface in R 3. For any two sets X, Y ⊂ R 3, let d(X, Y) denote the Euclidean distance between X and Y. The local feature size f(x) at a point x ∈ Σ is defined to be...
Approximating subtree distances between Phylogenies (2006)
Bonet Carbonell, Maria Luisa, St. John, Katherine, Mahindru, Ruchi, Amenta, Nina
We give a 5-approximation algorithm to the rooted Subtree-Prune-and-Regraft (rSPR) distance between two phylogenies, which was recently shown to be NP-complete by Bordewich and Semple [5]. This paper...
Complexity of Delaunay triangulation for points on lower-dimensional~polyhedra (2006)
Amenta, Nina, Attali, Dominique, Devillers, Olivier
We show that the Delaunay triangulation of a set of points distributed nearly uniformly on a polyhedron (not necessarily convex) of dimension p in d-dimensional space is of order n to the power...
Complexity of Delaunay triangulation for points on lower-dimensional~polyhedra (2006)
Amenta, Nina, Attali, Domiique, Devillers, Olivier
We show that the Delaunay triangulation of a set of points distributed nearly uniformly on a polyhedron (not necessarily convex) of dimension p in d-dimensional space is of order n to the power...
Complexity of Delaunay triangulation for points on lower-dimensional~polyhedra (2006)
Amenta, Nina, Attali, Dominique, Devillers, Olivier
We show that the Delaunay triangulation of a set of points distributed nearly uniformly on a polyhedron (not necessarily convex) of dimension p in d-dimensional space is of order n to the power...
Approximating Subtree Distances Between Phylogenies (2006)
Maria Luisa, Bonet Katherine, St. John, Ruchi Mahindru, Nina Amenta
We give a 5-approximation algorithm to the rooted Subtree-Prune-and-Regraft (rSPR) distance between two phylogenies, which was recently shown to be NP-complete by Bordewich and Semple [Bordewich and...
Hole Detection or: "How Much Geometry Hides in Connectivity?" (2006)
Funke, Stefan, Klein, Christian, Amenta, Nina, Cheong, Otfried
Wireless sensor networks typically consist of small, very simple network nodes without any positioning device like GPS. After an initialization phase, the nodes know with whom they can talk directly,...
The Effect of Corners on the Complexity of Approximate Range Searching (2006)
Arya, Sunil, Malamatos, Theocharis, Mount, David M., Amenta, Nina, Cheong, Otfried
Kutz, Martin, Amenta, Nina, Cheong, Otfried
We present an algorithm that computes a shortest non-contractible and a shortest non-separating cycle on an orientable combinatorial surface of bounded genus in $O(n log n)$ time, where $n$ denotes...
Approximating Subtree Distances Between Phylogenies (2005)
Maria Luisa, Bonet Katherine, St. John, Ruchi Mahindru, Nina Amenta
We give a 5-approximation algorithm to the rooted Subtree-Prune-and-Regraft (rSPR) distance between two phylogenies, which was recently shown to be NP-complete by Bordewich and Semple [5]. This paper...
David Wiley Nina, David F. Wiley, Nina Amenta, Dan A. Alcantara, Deboshmita Ghosh, Yong J. Kil, ...
We introduce a technique to visualize the gradual evolutionary change of the shapes of living things as a morph between known three-dimensional shapes. Given geometric computer models of anatomical...
The Domain of a Point Set Surface (2004)
M. Alexa, S. Rusinkiewicz, Nina Amenta, Yong J. Kil
It is useful to be able to define a two-dimensional point-set surface determined by a point cloud. One popular definition is Levin's MLS surface. This surface is defined on a domain which is a...
Defining point-set surfaces (2004)
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or direct...
Computational topology: ambient isotopic approximation of 2-manifolds (2003)
Nina Amenta, Thomas J. Peters, Er Russell
A fundamental issue in theoretical computer science is that of establishing unambiguous formal criteria for algorithmic output. This paper does so within the domain of computeraided geometric...
Computational topology: ambient isotopic approximation of 2-manifolds (2003)
Nina Amenta, Thomas J. Peters, Alexander Russell
A fundamental issue in theoretical computer science is that of establishing unambiguous formal criteria for algorithmic output. This paper does so within the domain of computeraided geometric...
Incremental Constructions con BRIO (2003)
Nina Amenta, Sunghee Choi, Günter Rote
Randomized incremental constructions are widely used in computational geometry, but they perform very badly on large data because of their inherently random memory access patterns. We define a biased...
A linear-time majority tree algorithm (2003)
Nina Amenta, Frederick Clarke, Katherine St. John
Abstract. We give a randomized linear-time algorithm for computing themajorityruleconsensustree.Themajorityruletreeiswidelyused for summarizing a set of phylogenetic trees, which is usually a...
A linear-time majority tree algorithm (2003)
Nina Amenta, Frederick Clarke, Katherine St. John
Abstract. We give a randomized linear-time algorithm for computing the majority rule consensus tree. The majority rule tree is widely used for summarizing a set of phylogenetic trees, which is...
Computational Topology: Ambient Isotopic Approximation of 2-Manifolds (2002)
Nina Amenta, Thomas J. Peters, Alexander Russell
A fundamental issue in theoretical computer science is that of establishing unambiguous formal criteria for algorithmic output. This paper does so within the domain of computeraided geometric...
The medial axis of a union of balls (2001)
Nina Amenta, Ravi Krishna Kolluri
We present an algorithm for computing the exact interior medial axis of a union of balls in IR d. Our algorithm combines the simple characterization of this medial axis given by Attali and Montanvert...
The Medial Axis of a Union of Balls (2001)
Nina Amenta, Ravi Krishna Kolluri
We present an algorithm for computing the exact interior medial axis of a union of balls in R^d. Our algorithm combines the simple characterization of this medial axis given by Attali and Montanvert...
A simple algorithm for homeomorphic surface reconstruction (2000)
Nina Amenta, Sunghee Choi, Tamal K. Dey, Naveen Leekha
The problem of computing a piecewise linear approximation to a surface from a set of sample points is important in solid modeling, computer graphics and computer vision. A recent algorithm [1] using...
Regression Depth and Center Points (2000)
Nina Amenta, Marshall Bern, David Eppstein, Shang-Hua Teng, N. Amenta, M. Bern, ...
. We show that, for any set of n points in d dimensions, there exists a hyperplane with regression depth at least #n/(d + 1)#, as had been conjectured by Rousseeuw and Hubert. Dually, for any...
The Power Crust, Unions of Balls, and the Medial Axis Transform (2000)
Nina Amenta, Sunghee Choi, Ravi Krishna Kolluri
The medial axis transform (or MAT) is a representation of an object as an infinite union of balls. We consider approximating the MAT of a three-dimensional object, and its complement, with a finite...
Accurate and Efficient Unions of Balls (2000)
Nina Amenta, Ravi Krishna Kolluri
Given a sample of points from the boundary of an object in IR 3 , we construct a representation of the object as a union of balls. We use many fewer balls than previous constructions, but our shape...
Emerging Challenges in Computational Topology (1999)
Bern, Marshall, Eppstein, David, Agarwal, Pankaj K., Amenta, Nina, Chew, Paul, Dey, Tamal, ...
Here we present the results of the NSF-funded Workshop on Computational Topology, which met on June 11 and 12 in Miami Beach, Florida. This report identifies important problems involving both...
One-pass Delaunay filtering for homeomorphic 3D surface reconstruction (1999)
We give a simple algorithm for surface reconstruction from a set of point samples in R 3, using only one three-dimensional Voronoi diagram computation. We also give a fairly simple proof that the...
Emerging challenges in computational topology (1999)
Marshall Bern, Pankaj K. Agarwal, Nina Amenta, Paul Chew, Tamal Dey, David P. Dobkin, ...
Here we present the results of the NSF-funded Workshop on Computational Topology, which met on June 11 and 12 in Miami Beach, Florida. This report identifies
Surface reconstruction by Voronoi filtering (1999)
We give a simple combinatorial algorithm that computes a piecewise-linear approximation of a smooth surface from a finite set of sample points. The algorithm uses Voronoi vertices to remove triangles...
Emerging Challenges in Computational Topology (1999)
Marshall Bern, David Eppstein, Pankaj K. Agarwal, Nina Amenta, Paul Chew, Tamal Dey, ...
Here we present the results of the NSF-funded Workshop on Computational Topology, which met on June 11 and 12 in Miami Beach, Florida. This report identifies important problems involving both...
One-Pass Delaunay Filtering for Homeomorphic 3D Surface Reconstruction (1999)
We give a simple algorithm for surface reconstruction from a set of point samples in R 3 , using only one three-dimensional Voronoi diagram computation. We also give a fairly simple proof that the...
Optimal Point Placement for Mesh Smoothing (1998)
Amenta, Nina, Bern, Marshall, Eppstein, David
We study the problem of moving a vertex in an unstructured mesh of triangular, quadrilateral, or tetrahedral elements to optimize the shapes of adjacent elements. We show that many such problems can...
Regression Depth and Center Points (1998)
Amenta, Nina, Bern, Marshall, Eppstein, David, Teng, Shang-Hua
We show that, for any set of n points in d dimensions, there exists a hyperplane with regression depth at least ceiling(n/(d+1)). as had been conjectured by Rousseeuw and Hubert. Dually, for any...
Largest placement of one convex polygon inside another (1998)
Pankaj K. Agarwal, Nina Amenta, Micha Sharir
We show that the largest similar copy of a convex polygon P with m edges inside a convex polygon Q with n edges can be computed in O(mn 2 log n) time. We also show that the combinatorial complexity...
A New Voronoi-Based Surface Reconstruction Algorithm (1998)
Nina Amenta Ut, Nina Amenta, Marshall Bern
We describe our experience with a new algorithm for the reconstruction of surfaces from unorganized sample points in IR 3 .Thealgorithm is the first for this problem with provable guarantees. Given a...
Regression Depth and Center Points (1998)
Nina Amenta, Marshall Bern, David Eppstein, Shang-Hua Teng
this paper is on the xxx.lanl.gov e-print server, cs.CG/9809037.
The Crust and the Beta-Skeleton: Combinatorial Curve Reconstruction (1998)
Nina Amenta, Marshall Bern, David Eppstein
We construct a graph on a planar point set, which captures its shape in the following sense: if a smooth curve is sampled densely enough, the graph on the samples is a polygonalization of the curve,...
ARTICLE NO. IP980465 The Crust and the β-Skeleton: Combinatorial Curve Reconstruction (1997)
We construct a graph on a planar point set, which captures its shape in the following sense: if a smooth curve is sampled densely enough, the graph on the samples is a polygonalization of the curve,...
Optimal Point Placement for Mesh Smoothing (1997)
Nina Amenta, Marshall Bern, David Eppstein
We study the problem of moving a vertex in a finite element mesh to optimize the shapes of adjacent triangles. We show that many such problems can be solved in linear time using generalized linear...
Optimal point placement for mesh smoothing (1997)
We study the problem of moving a vertex in an unstructured mesh of triangular, quadrilateral, or tetrahedral elements to optimize the shapes of adjacent elements. We show that many such problems can...
ARTICLE NO. IP980465 The Crust and the β-Skeleton: Combinatorial Curve Reconstruction (1997)
We construct a graph on a planar point set, which captures its shape in the following sense: if a smooth curve is sampled densely enough, the graph on the samples is a polygonalization of the curve,...
Largest Placement of One Convex Polygon inside Another (1996)
Pankaj Agarwal Nina, Pankaj Agarwal, Pankaj K. Agarwal, Pankaj K. Agarwal, Nina Amenta, ...
We show that the largest similar copy of a convex polygon P with m edges inside a convex polygon Q with n edges can be computed in O(mn 2 log n) time. We also show that the combinatorial complexity...
Application Challenges to Computational Geometry (1996)
With rapid advances in computer hardware and visualization systems, geometric computing is creeping into virtually every corner of science and engineering, from design and manufacturing to...
Deformed Products and Maximal Shadows of Polytopes (1996)
Nina Amenta, Günter M. Ziegler
We present a construction of deformed products of polytopes that has as special cases all the known constructions of linear programs with "many pivots," starting with the famous Klee-Minty...
Largest Placement of One Convex Polygon inside Another (1996)
Pankaj Agarwal Nina, Pankaj K. Agarwal, Nina Amenta, Micha Sharir
We show that the largest similar copy of a convex polygon P with m edges inside a convex polygon Q with n edges can be computed in O(mn 2 log n) time. We also show that the combinatorial complexity...
Largest Placements and Motion Planning of a Convex Polygon (1996)
Pankaj K. Agarwal, Nina Amenta, Boris Aronov, Micha Sharir
We study two problems involving collision-free placements of a convex m-gon P in a planar polygonal environment: (i) We first show that the largest similar copy of P inside another convex polygon Q...
Helly-type Theorems and Generalized Linear Programming (1994)
Recent combinatorial algorithms for linear programming can also be applied to certain nonlinear problems. We call these Generalized Linear Programming, or GLP, problems. We connect this class to a...