NDLI: Lenses in arrangements of pseudo-circles and their applications

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

Parametric search made practical

A local search approximation algorithm for k-means clustering

On the crossing number of complete graphs

On the number of embeddings of minimally rigid graphs

Collision detection for deforming necklaces

Efficient maintenance and self-collision testing for Kinematic Chains

Box-trees for collision checking in industrial installations

Finite metric spaces: combinatorics, geometry and algorithms

Finding the consensus shape for a protein family

Paper position sensing

A global approach to automatic solution of jigsaw puzzles

The power of nonmonotonicity in geometric searching

A lower bound on the distortion of embedding planar metrics into Euclidean space

The one-round Voronoi game

Approximate nearest neighbor algorithms for Frechet distance via product metrics

Point-line incidences in space

Incidences between points and circles in three and higher dimensions

Lenses in arrangements of pseudo-circles and their applications

Pseudotriangulations, polytopes, and how to expand linkages

Guaranteed: quality parallel delaunay refinement for restricted polyhedral domains

The Delaunay tetrahedralization from Delaunay triangulated surfaces

Quickest paths, straight skeletons, and the city Voronoi diagram

Testing Homotopy for paths in the plane

Pseudo approximation algorithms, with applications to optimal motion planning

Kinetic maintenance of context-sensitive hierarchical representations for disjoint simple polygons

Interlocked open linkages with few joints

Conforming Delaunay triangulations in 3D

The probabilistic complexity of the Voronoi diagram of points on a polyhedron

Three dimensional euclidean Voronoi diagrams of lines with a fixed number of orientations

Polyhedral Voronoi diagrams of polyhedra in three dimensions

Vertex-unfoldings of simplicial manifolds

Optimally cutting a surface into a disk

Optimal decomposition of polygonal models into triangle strips

Hybrid meshes: multiresolution using regular and irregular refinement

Exact minkowski sums and applications

Homotopy techniques for real-time visualization of geometric tangent problems

Growing fat graphs

AUTO-FOLLOW: getting a piece of the action all the time

Adventures of Möbius band: mathematical visualization in virtual environment

Improved construction of vertical decompositions of three-dimensional arrangements

Cost prediction for ray shooting

Visibility preserving terrain simplification: an experimental study

Projective clustering in high dimensions using core-sets

Lenses in arrangements of pseudo-circles and their applications

Content Provider	ACM Digital Library
Author	Pach, János Smorodinsky, Shakhar Sharir, Micha Pinchasi, Rom Nevo, Eran
Abstract	(MATH) A collection of simple closed Jordan curves in the plane is called a family of pseudo-circles if any two of its members intersect at most twice. A closed curve composed of two subarcs of distinct pseudo-circles is said to be an empty lens if it does not intersect any other member of the family. We establish a linear upper bound on the number of empty lenses in an arrangement of n pseudo-circles with the property that any two curves intersect precisely twice. Enhancing this bound in several ways, and combining it with the technique of Tamaki and Tokuyama [16], we show that any collection of n pseudo-circles can be cut into \$\bx\$ arcs so that any two intersect at most once, provided that the given pseudo-circles are x-monotone and admit an algebraic representation by three real parameters; here \$\alpha(n)\$ is the inverse Ackermann function, and s is a constant that depends on the algebraic degree of the representation of the pseudo-circles (s=2 for circles and parabolas). For arbitrary collections of pseudo-circles, any two of which intersect twice, the number of necessary cuts reduces to O(n $^{4/3}).$ As applications, we obtain improved bounds for the number of point-curve incidences, the complexity of a single level, and the complexity of many faces in arrangements of circles, pairwise intersecting pseudo-circles, parabolas, and families of homothetic copies of a fixed convex curve. We also obtain a variant of the Gallai-Sylvester theorem for arrangements of pairwise intersecting pseudo-circles, and a new lower bound for the number of distinct distances among n points in the plane under any simply-defined norm or convex distance function.
Starting Page	123
Ending Page	132
Page Count	10
File Format	PDF
ISBN	1581135041
DOI	10.1145/513400.513417
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2002-06-05
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Pseudo-circles Arrangements Levels Incidences Distinct distances Lenses
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