NDLI: On simultaneous inner and outer approximation of shapes

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

Cutting hyperplane arrangements

Some new bounds for Epsilon-nets

How to net a lot with little: small ε-nets for disks and halfspaces

Quasi-optimal upper bounds for simplex range searching and new zone theorems

Polygon triangulation in O(n log log n) time with simple data-structures

An O(n2log n) time algorithm for the MinMax angle triangulation

Structured visibility profiles with applications to problems in simple polygons (extended abstract)

Minimum-link paths among obstacles in the plane

Parallel methods for visibility and shortest path problems in simple polygons (preliminary version)

The combinatorial complexity of hyperplane transversals

On the limited power of linear probes and other optimization oracles

Computational complexity of combinatorial surfaces

Points and triangles in the plane and halving planes in space

Slimming down by adding; selecting heavily covered points

Tiling the plane with one tile

A trivial knot whose spanning disks have exponential size

Geometric computations with algebraic varieties of bounded degree

On computing the intersection of B-splines (extended abstract)

Merging visibility maps

Stabbing and ray shooting in 3 dimensional space

K-d trees for semidynamic point sets

On the optimal bisection of a polygon (extended abstract)

Euclidean minimum spanning trees and bichromatic closest pairs

Linear programming and convex hulls made easy

On simultaneous inner and outer approximation of shapes

Maximin location of convex objects in a polygon and related dynamic Voronoi diagrams

Constructing strongly convex hulls using exact or rounded arithmetic

Finding compact coordinate representations for polygons and polyhedra

Some provably hard crossing number problems

Enumeration and visibility problems in integer lattices (extended abstract)

An exact algorithm for kinodynamic planning in the plane

Approximate motion planning and the complexity of the boundary of the union of simple geometric figures

Provably good approximation algorithms for optimal kinodynamic planning for Cartesian robots and open chain manipulators

Shortest rectilinear paths among weighted obstacles

On minimal rectilinear Steiner trees in all dimensions

Selecting distances in the plane

Reconstructing sets from interpoint distances (extended abstract)

Computing the minimum Hausdorff distance for point sets under translation

On solving geometric optimization problems using shortest paths

Shortest paths on a polyhedron

A computational geometry workbench

On simultaneous inner and outer approximation of shapes

Content Provider	ACM Digital Library
Author	Fleischer, Rudolf Welzl, Emo Rote, Günter Mehlhorn, Kurt Yap, Chee
Abstract	For compact Euclidean bodies P, Q, we define λ(P, Q) to be smallest ratio r/s where r > 0, s > 0 satisfy sQ′ ⊆ P ⊆ rQ″. Here sQ denotes a scaling of Q by factor s, and Q′, Q″ are some translates of Q. This function λ gives us a new distance function between bodies which, unlike previously studied measures, is invariant under affine transformations. If homothetic bodies are identified, the logarithm of this function is a metric. (Two bodies are homothetic if one can be obtained from the other by scaling and translation).For integer &kgr; ≥ 3, define λ(&kgr;) to be the minimum value such that for each convex polygon P there exists a convex &kgr;-gon Q with λ(P, Q) ≤ λ(&kgr;). Among other results, we prove that 2.118… ≤ λ(3) ≤ 2.25 and λ(&kgr;) = 1 + &THgr;(&kgr;-2). We give an &Ogr;(n2 log2 n) time algorithm which for any input convex n-gon P, finds a triangle T that minimizes λ(T, P) among triangles. But in linear time, we can find a triangle t with λ(t, P) ≤ 2.25.Our study is motivated by the attempt to reduce the complexity of the polygon containment problem, and also the motion planning problem. In each case, we describe algorithms which will run faster when certain implicit slackness parameters of the input are bounded away from 1. These algorithms illustrate a new algorithmic paradigm in computational geometry for coping with complexity.
Starting Page	216
Ending Page	224
Page Count	9
File Format	PDF
ISBN	0897913620
DOI	10.1145/98524.98572
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1990-05-01
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

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

Visit at cerfacs (1995).

Inner and outer clustering approximations of belief structures (2000).

Outer Approximation and Outer-Inner Approximation Approaches for Unit Commitment Problem

An Inner-Outer Approximation Approach to Chance Constrained Optimization

Evaluation of Different Tools of Precision Finishing for Sun Gear with Inner-Outer Tooth Shapes.

An outer-inner approximation for separable minlps.

Inner And Outer Approximation Of Belief Structures Using A Hierarchical Clustering Approach (2001)

Best Simultaneous Approximation of Finite Set in Inner Product Space

An Outer-Inner Approximation for separable MINLPs

On simultaneous inner and outer approximation of shapes

Similar Documents

Visit at cerfacs (1995).

Inner and outer clustering approximations of belief structures (2000).

Outer Approximation and Outer-Inner Approximation Approaches for Unit Commitment Problem

An Inner-Outer Approximation Approach to Chance Constrained Optimization

Evaluation of Different Tools of Precision Finishing for Sun Gear with Inner-Outer Tooth Shapes.

An outer-inner approximation for separable minlps.

Inner And Outer Approximation Of Belief Structures Using A Hierarchical Clustering Approach (2001)

Best Simultaneous Approximation of Finite Set in Inner Product Space

An Outer-Inner Approximation for separable MINLPs

On simultaneous inner and outer approximation of shapes