Automatically assigned DDC number: 0066

Manually assigned DDC number: 0066

Number of references: 4

Title: Surface Approximation and Geometric Partitions

Author:

Author:

Subject: Pankaj K. Agarwal,Subhash Suri Surface Approximation and Geometric Partitions

Description: Motivated by applications in computer graphics, visualization, and scientific computation, we study the computational complexity of the following problem: Given a set S of n points sampled from a bivariate function f(x; y) and an input parameter " ? 0, compute a piecewise-linear function Sigma(x; y) of minimum complexity (that is, a xy-monotone polyhedral surface, with a minimum number of vertices, edges, or faces) such that jSigma(x p ; y p ) Gamma z p j "; for all (x p ; y p ; z p ) 2 S: We prove that the decision version of this problem is NP-Hard . The main result of our paper is a polynomial-time approximation algorithm that computes a piecewise-linear surface of size O(K o log K o ), where K o is the complexity of an optimal surface satisfying the constraints of the problem. The technique developed in our paper is more general and applies to several other problems that deal with partitioning of points (or other objects) subject to certain geometric constraints. For instan...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1996-06-07

Pubyear: 1996

Format: ps

Identifier: http://citeseer.ist.psu.edu/150193.html

Source: http://www.cs.duke.edu/~pankaj/papers/surface-approx.ps.gz

Language: en

Relation:

Relation:

Relation:

Relation:

Rights: unrestricted

Graph

<?xml   version="1.0"   encoding="UTF-8"?>

<references_metadata>

      <rec   ID="/368170.html"   Type="article"   CiteSeer_Book="International   Journal   of   Computational   Geometry   and   Applications"   CiteSeer_Volume="8"   Title="Decision   trees   for   geometric   models,">

            <identifier   Org="ISBN:0819413259"   Paper_ID="/368170.html"   Extracted="0819413259"   DDC="006.4/2/01516"   Normalized_DDC="0064201516"   Normalized_Weight="0.16666666666666666"   />

            <identifier   Org="ISBN:0819416916"   Paper_ID="/368170.html"   Extracted="0819416916"   />

            <identifier   Org="ISBN:0898713293"   Paper_ID="/368170.html"   Extracted="0898713293"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.16666666666666666"   />

            <identifier   Org="ISBN:1584883014"   Paper_ID="/368170.html"   Extracted="1584883014"   DDC="516/.13"   Normalized_DDC="51613"   Normalized_Weight="0.16666666666666666"   />

            <identifier   Org="ISBN:3540428755"   Paper_ID="/368170.html"   Extracted="3540428755"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.16666666666666666"   />

            <identifier   Org="ISBN:3540571558"   Paper_ID="/368170.html"   Extracted="3540571558"   DDC="005.7/3"   Normalized_DDC="00573"   Normalized_Weight="0.16666666666666666"   />

            <identifier   Org="ISBN:354061785X"   Paper_ID="/368170.html"   Extracted="354061785X"   DDC="516/.00285"   Normalized_DDC="51600285"   Normalized_Weight="0.16666666666666666"   />

            <identifier   Org="ISBN:3540853626"   Paper_ID="/368170.html"   Extracted="3540853626"   />

      </rec>

      <rec   ID="/480945.html"   Type="article"   CiteSeer_Book="Computer   Aided   Geometric   Design"   CiteSeer_Volume="5"   Title="Polygonization   of   Implicit   Surfaces,">

            <identifier   Org="ISBN:0123361559"   Paper_ID="/480945.html"   Extracted="0123361559"   DDC="006.6/6"   Normalized_DDC="00666"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:0444886834"   Paper_ID="/480945.html"   Extracted="0444886834"   />

            <identifier   Org="ISBN:0769521711"   Paper_ID="/480945.html"   Extracted="0769521711"   />

            <identifier   Org="ISBN:0792307240"   Paper_ID="/480945.html"   Extracted="0792307240"   DDC="516.3/52"   Normalized_DDC="516352"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:0819405566"   Paper_ID="/480945.html"   Extracted="0819405566"   DDC="621.36/7"   Normalized_DDC="621367"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:1568810393"   Paper_ID="/480945.html"   Extracted="1568810393"   DDC="516.3/52"   Normalized_DDC="516352"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:1568813503"   Paper_ID="/480945.html"   Extracted="1568813503"   />

            <identifier   Org="ISBN:1581135068"   Paper_ID="/480945.html"   Extracted="1581135068"   />

            <identifier   Org="ISBN:1581138520"   Paper_ID="/480945.html"   Extracted="1581138520"   />

            <identifier   Org="ISBN:3211837116"   Paper_ID="/480945.html"   Extracted="3211837116"   />

            <identifier   Org="ISBN:3540220577"   Paper_ID="/480945.html"   Extracted="3540220577"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:3540221158"   Paper_ID="/480945.html"   Extracted="3540221158"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:3540258620"   Paper_ID="/480945.html"   Extracted="3540258620"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:3540401563"   Paper_ID="/480945.html"   Extracted="3540401563"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:3540620052"   Paper_ID="/480945.html"   Extracted="3540620052"   DDC="006.6/01/516"   Normalized_DDC="006601516"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:3540738428"   Paper_ID="/480945.html"   Extracted="3540738428"   DDC="516"   Normalized_DDC="516"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:3540768351"   Paper_ID="/480945.html"   Extracted="3540768351"   />

            <identifier   Org="ISBN:9051991878"   Paper_ID="/480945.html"   Extracted="9051991878"   />

            <identifier   Org="ISBN:9051991967"   Paper_ID="/480945.html"   Extracted="9051991967"   DDC="005.275"   Normalized_DDC="005275"   Normalized_Weight="0.09090909090909091"   />

      </rec>

      <rec   ID="/61392.html"   Type="article"   CiteSeer_Book="Computers   and   Graphics"   CiteSeer_Volume="15"   Title="Simplification   of   objects   rendered   by   polygonal   approximations,">

            <identifier   Org="ISBN:0201325578"   Paper_ID="/61392.html"   Extracted="0201325578"   DDC="006"   Normalized_DDC="006"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:0309051355"   Paper_ID="/61392.html"   Extracted="0309051355"   DDC="006"   Normalized_DDC="006"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:0780331273"   Paper_ID="/61392.html"   Extracted="0780331273"   />

            <identifier   Org="ISBN:0780336747"   Paper_ID="/61392.html"   Extracted="0780336747"   DDC="006.6"   Normalized_DDC="0066"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:0780339495"   Paper_ID="/61392.html"   Extracted="0780339495"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:0818675187"   Paper_ID="/61392.html"   Extracted="0818675187"   />

            <identifier   Org="ISBN:0818678437"   Paper_ID="/61392.html"   Extracted="0818678437"   DDC="006"   Normalized_DDC="006"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:0818680288"   Paper_ID="/61392.html"   Extracted="0818680288"   DDC="006.6"   Normalized_DDC="0066"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:0818682620"   Paper_ID="/61392.html"   Extracted="0818682620"   DDC="621.367"   Normalized_DDC="621367"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:0819436224"   Paper_ID="/61392.html"   Extracted="0819436224"   DDC="616.07/54"   Normalized_DDC="6160754"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:0897918843"   Paper_ID="/61392.html"   Extracted="0897918843"   DDC="006.6"   Normalized_DDC="0066"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:0898713293"   Paper_ID="/61392.html"   Extracted="0898713293"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:1568812469"   Paper_ID="/61392.html"   Extracted="1568812469"   DDC="006.6"   Normalized_DDC="0066"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:1581131410"   Paper_ID="/61392.html"   Extracted="1581131410"   />

            <identifier   Org="ISBN:9051994451"   Paper_ID="/61392.html"   Extracted="9051994451"   DDC="810.2856"   Normalized_DDC="8102856"   Normalized_Weight="0.08333333333333333"   />

      </rec>

      <rec   ID="/244582.html"   Type="article"   CiteSeer_Book="Computer   Graphics"   CiteSeer_Volume="26"   Title="Decimation   of   triangle   meshes,">

            <identifier   Org="ISBN:012387582X"   Paper_ID="/244582.html"   Extracted="012387582X"   DDC="006.6"   Normalized_DDC="0066"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:0444511040"   Paper_ID="/244582.html"   Extracted="0444511040"   DDC="006.6"   Normalized_DDC="0066"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:0818682620"   Paper_ID="/244582.html"   Extracted="0818682620"   DDC="621.367"   Normalized_DDC="621367"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:0968880800"   Paper_ID="/244582.html"   Extracted="0968880800"   />

            <identifier   Org="ISBN:1860583253"   Paper_ID="/244582.html"   Extracted="1860583253"   DDC="670.427"   Normalized_DDC="670427"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540221298"   Paper_ID="/244582.html"   Extracted="3540221298"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:354023957X"   Paper_ID="/244582.html"   Extracted="354023957X"   DDC="629.892"   Normalized_DDC="629892"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540294112"   Paper_ID="/244582.html"   Extracted="3540294112"   DDC="616.07540285"   Normalized_DDC="61607540285"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540413960"   Paper_ID="/244582.html"   Extracted="3540413960"   DDC="006.6/01/516"   Normalized_DDC="006601516"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:354042301X"   Paper_ID="/244582.html"   Extracted="354042301X"   DDC="005.74"   Normalized_DDC="00574"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:354043593X"   Paper_ID="/244582.html"   Extracted="354043593X"   DDC="004"   Normalized_DDC="004"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540436391"   Paper_ID="/244582.html"   Extracted="3540436391"   DDC="516"   Normalized_DDC="516"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540651578"   Paper_ID="/244582.html"   Extracted="3540651578"   DDC="616.0757"   Normalized_DDC="6160757"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540714561"   Paper_ID="/244582.html"   Extracted="3540714561"   DDC="006.3/7"   Normalized_DDC="00637"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3540748725"   Paper_ID="/244582.html"   Extracted="3540748725"   DDC="790.20285"   Normalized_DDC="79020285"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:3898380343"   Paper_ID="/244582.html"   Extracted="3898380343"   DDC="006.42"   Normalized_DDC="00642"   Normalized_Weight="0.06666666666666667"   />

            <identifier   Org="ISBN:905809636X"   Paper_ID="/244582.html"   Extracted="905809636X"   />

      </rec>

      <rec   ID="SELF"   Type="SELF"   CiteSeer_Book="SELF"   CiteSeer_Volume="SELF"   Title="Surface   Approximation   and   Geometric   Partitions">

            <identifier   Org="ISBN:0521848628"   Paper_ID="SELF"   Extracted="0521848628"   DDC="516/.11"   Normalized_DDC="51611"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:0780331273"   Paper_ID="SELF"   Extracted="0780331273"   />

            <identifier   Org="ISBN:0792369572"   Paper_ID="SELF"   Extracted="0792369572"   DDC="004/.35"   Normalized_DDC="00435"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:0818682620"   Paper_ID="SELF"   Extracted="0818682620"   DDC="621.367"   Normalized_DDC="621367"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:0819436224"   Paper_ID="SELF"   Extracted="0819436224"   DDC="616.07/54"   Normalized_DDC="6160754"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:0898713293"   Paper_ID="SELF"   Extracted="0898713293"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:089871558X"   Paper_ID="SELF"   Extracted="089871558X"   />

            <identifier   Org="ISBN:1598297929"   Paper_ID="SELF"   Extracted="1598297929"   />

            <identifier   Org="ISBN:3540200533"   Paper_ID="SELF"   Extracted="3540200533"   DDC="516.3/52"   Normalized_DDC="516352"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:3540240586"   Paper_ID="SELF"   Extracted="3540240586"   DDC="005.3"   Normalized_DDC="0053"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:3540602208"   Paper_ID="SELF"   Extracted="3540602208"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:3540654313"   Paper_ID="SELF"   Extracted="3540654313"   DDC="519.3"   Normalized_DDC="5193"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:3540782745"   Paper_ID="SELF"   Extracted="3540782745"   DDC="621.36/7"   Normalized_DDC="621367"   Normalized_Weight="0.09090909090909091"   />

            <identifier   Org="ISBN:3898380343"   Paper_ID="SELF"   Extracted="3898380343"   DDC="006.42"   Normalized_DDC="00642"   Normalized_Weight="0.09090909090909091"   />

      </rec>

</references_metadata>

www.000webhost.com