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

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

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

Content Provider	ACM Digital Library
Author	Glisse, Marc Lazard, Sylvain
Abstract	We present two new fundamental lower bounds on the worst-case combinatorial complexity of sets of free lines and sets of maximal free line segments in the presence of balls in three dimensions. We first prove that the set of maximal non-occluded line segments among n disjoint unit balls has complexity $©(n^{4}),$ which matches the trivial $O(n^{4})$ upper bound. This improves the trivial $©(n^{2})$ bound and also the $©(n^{3})$ lower bound for the restricted setting of arbitrary-size balls [Devillers and Ramos, 2001]. This result settles, negatively, the natural conjecture that this set of line segments, or, equivalently, the visibility complex, has smaller worst-case complexity for disjoint fat objects than for skinny triangles. We also prove an $©(n^{3})$ lower bound on the complexity of the set of non-occluded lines among n balls of arbitrary radii, improving on the trivial $©(n^{2})$ bound. This new bound almost matches the recent $O(n^{3+µ})$ upper bound [Rubin, 2010].
Starting Page	48
Ending Page	57
Page Count	10
File Format	PDF
ISBN	9781450300162
DOI	10.1145/1810959.1810969
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2010-06-13
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Visibility complex Free lines Free segments 3d visibility Balls
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