NDLI: Optimal reconstruction might be hard

Please wait, while we are loading the content...

Optimal partition trees

Discrete geometric structures for architecture

Better bounds on the union complexity of locally fat objects

Adding one edge to planar graphs makes crossing number hard

Visualizing 3D Euler spirals

A geometric approach to collective motion

Output-sensitive algorithm for the edge-width of an embedded graph

A traveller's problem

The complexity of the normal surface solution space

Klee's measure problem on fat boxes in time $∂(n^{(d+2)/3})$

The tidy set: a minimal simplicial set for computing homology of clique complexes

On degrees in random triangulations of point sets

Manifold reconstruction using tangential Delaunay complexes

Improving the first selection lemma in $R^{3}$

Applications of geometry and topology for quadrilateral meshprocessing and verifiable visualization

Computing planar Voronoi diagrams in double precision: a further example of degree-driven algorithm design

Incidences in three dimensions and distinct distances in the plane

Consistent digital line segments

On the complexity of sets of free lines and line segments among balls in three dimensions

Planar visibility: testing and counting

Shape approximation using k-order alpha-hulls

Kinetic stable Delaunay graphs

Finding shortest non-trivial cycles in directed graphs on surfaces

A constant-factor approximation algorithm for TSP with pairwise-disjoint connected neighborhoods in the plane

Distance k-sectors exist

An improved algorithm for computing the volume of the union of cubes

A randomized O(m log m) time algorithm for computing Reeb graphs of arbitrary simplicial complexes

Acute triangulations of polyhedra and the Euclidean space

Optimal reconstruction might be hard

Points with large quadrant-depth

3D Euler spirals for 3D curve completion

Tangencies between families of disjoint regions in the plane

The geometry of flocking

Lines avoiding balls in three dimensions revisited

The 2-center problem in three dimensions

Constructing Reeb graphs using cylinder maps

A kinetic triangulation scheme for moving points in the plane

Approximating loops in a shortest homology basis from point data

New constructions of SSPDs and their applications

Zone diagrams in Euclidean spaces and in other normed spaces

Orthogonal range reporting: query lower bounds, optimal structures in 3-d, and higher-dimensional improvements

Topological inference via meshing

Dynamic well-spaced point sets

Reconstructing shapes with guarantees by unions of convex sets

Approximating the Fréchet distance for realistic curves in near linear time

I/O-efficient computation of water flow across a terrain

Steinitz theorems for orthogonal polyhedra

Tight lower bounds for halfspace range searching

Linkless and flat embeddings in 3-space and the unknot problem

Convexification of polygons by length preserving transformations

A dynamic data structure for approximate range searching

Geometric tomography with topological guarantees

Computing similarity between piecewise-linear functions

Geometric methods for multi-agent collision avoidance

Optimal reconstruction might be hard

Content Provider	ACM Digital Library
Author	Attali, Dominique Lieutier, André
Abstract	Sampling conditions for recovering the homology of a set using topological persistence are much weaker than sampling conditions required by any known polynomial time algorithm for producing a topologically correct reconstruction. Under the former sampling conditions which we call weak sampling conditions, we give an algorithm that outputs a topologically correct reconstruction. Unfortunately, even though the algorithm terminates, its time complexity is unbounded. Motivated by the question of knowing if a polynomial time algorithm for reconstruction exists under the weak sampling conditions, we identify at the heart of our algorithm a test which requires answering the following question: given two 2-dimensional simplicial complexes L ⊂ K, does there exist a simplicial complex containing L and contained in K which realizes the persistent homology of L into K? We call this problem the homological simplification of the pair (K, L) and prove that this problem is NP-complete, using a reduction from 3SAT.
Starting Page	334
Ending Page	343
Page Count	10
File Format	PDF
ISBN	9781450300162
DOI	10.1145/1810959.1811014
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2010-06-13
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Homological simplification Sampling conditions Topological persistence 3sat Shape reconstruction Np-completeness
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in